CT50834

The Crowhaven Disorder Count

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the rookery of Crowhaven close for winter, Zoya must finish the registers ledger - one figure at a time. Task: Print the number of inversions: index pairs (i,j) with i<j but a[i] > a[j]. Input format: First line: n. Second line: n integers. Output format: Print the inversion count (fits 64-bit). Constraints: 1 <= n <= 1416; 0 <= a[i],x <= 1000000.

Example 1:

Input: 277 923627 511148 138935 365196 405134 417660 337088 755027 332434 81305 975911 694993 686399 166033 223430 454337 133239 741625 789629 876765 750875 525336 267825 648238 446457 376923 724300 670342 543886 571477 76334 845804 503102 107408 389275 254850 2168 666496 889326 416373 368283 32729 778737 795320 2523 797977 611934 710158 932410 909325 19838 624346 786190 598609 593227 381946 908336 366911 603066 516803 436119 3467 844958 738621 96295 339384 104582 521691 193742 430900 137439 647226 167902 631241 266256 898896 818306 277138 722629 689057 404942 651848 427520 883118 858218 670797 489485 323919 382501 414713 233538 144116 338760 689680 988437 338081 534427 349852 847292 925394 730982 392810 248085 130137 480683 775023 353180 856638 26408 993790 731236 555144 486387 571040 88362 9002…
Output: 18922

Example 2:

Input: 743 711 569 258 354 736 695 466 123 336 93 433 172 411 60 402 584 1 214 603 268 226 320 23 734 380 164 37 199 361 725 181 63 250 56 592 84 3 11 106 67 618 497 98 51 541 723 645 617 636 637 34 327 330 456 228 593 542 679 480 7 333 290 556 580 727 662 8 659 110 151 351 470 633 449 689 445 588 282 627 526 594 12 500 47 650 735 634 304 545 688 73 309 534 536 646 254 436 441 652 397 426 690 321 596 43 582 408 439 137 247 78 91 693 369 703 573 669 331 575 236 192 589 343 230 6 346 686 335 420 17 231 437 27 386 281 665 585 58 323 415 284 193 663 237 553 241 706 424 607 412 543 86 622 66 71 467 208 393 204 515 173 566 94 469 419 705 572 222 654 404 271 83 719 417 428 649 680 177 233 15 175 344 316 113 457 722 392 105 448 49 447 425 635 55 604 74 149 528 413 529 202 311 560 537 324 292 90 183 673 1…
Output: 139028

Example 3:

Input: 432 142653 222215 591759 493177 950214 928434 954052 773199 969815 660599 712578 207722 648470 552999 964776 753500 399227 167635 716233 30843 517121 539588 803226 828187 297076 866523 24714 740708 462936 45218 340078 944056 89949 123627 774722 119939 549470 188296 48224 955679 934802 131807 516878 553176 763569 543014 774788 924900 741085 290101 595522 575877 303229 888505 304986 415842 860553 844928 718208 637126 215157 911022 182335 936185 130120 668603 857929 63693 663514 370216 431193 99871 241681 69217 677059 472511 215301 772235 24673 162208 322883 751817 429393 462748 801635 695737 885138 938326 52837 618377 815405 988876 616060 621858 11647 418031 275757 920428 249118 710255 685782 561242 335366 821503 640127 407550 131970 980612 819982 154733 155168 925273 404764 705882 403525 94…
Output: 47911

Constraints:

1 <= n <= 1416; 0 <= a[i],x <= 1000000.

Loading...
Test Cases:No test cases
No test cases available.
The Crowhaven Disorder Count - MEDIUM Coding Problem | CodeTikki