CT56380

Wade's vials Disorder Count

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the desert outpost of Sandspire opens only for a perfect tally of vials. Wade means to find out. 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 <= 1087; 0 <= a[i],x <= 1000000.

Example 1:

Input: 1043 144271 833158 688447 31523 198036 376637 542771 446953 295636 476276 163081 402577 639844 902447 612316 247185 573067 533685 992902 440037 672894 124657 524211 260840 154002 586831 742725 154945 697693 633535 513364 204140 902494 324229 253594 896644 61256 786729 807003 533129 467350 799227 811364 125932 304287 793798 43631 315231 16084 976894 143251 82103 696094 588980 862853 834176 330139 954867 389291 444947 59164 435540 272065 961900 204902 875867 183454 404245 290266 770730 385723 892189 314720 482706 510255 196463 740780 982595 269603 450499 91018 272386 77943 634961 893254 68528 963736 793325 198747 815312 797169 124984 278641 416519 227567 841936 717191 654611 579662 896008 661207 436552 137441 893765 244815 535800 925678 172131 403030 486611 758208 147217 841383 959416 698180…
Output: 271765

Example 2:

Input: 58 262934 658062 379994 281169 962000 52530 480986 65072 63859 148394 300538 886260 592042 883895 775190 291463 787472 846427 184919 964026 39057 28421 363739 3653 809144 10635 17710 383670 572627 599215 876001 371711 506635 468479 473358 269437 21442 524399 518027 459018 254155 98099 440488 403241 913153 981479 668872 516323 682177 545148 853670 861094 144642 616139 214343 336246 3961 54038
Output: 808

Example 3:

Input: 1020 560468 831120 368057 426283 459756 745699 275888 107482 668798 922956 458343 549555 191543 786912 241050 439834 856334 997191 129517 434317 789738 749580 255118 261623 726690 734906 419033 64833 108019 767694 38229 727696 223328 476899 115845 858333 801669 216848 463448 10138 559196 149720 990052 878149 107597 369396 375956 845887 490399 736070 569795 767244 457640 598374 271901 905202 331570 698955 849586 514511 421752 479674 292789 239745 353515 711881 532829 811551 105606 758027 532105 861601 606574 97214 52844 449422 69621 847817 258717 169567 137153 198513 915255 403383 829214 262686 97588 812455 615523 378098 276619 177492 724368 587843 804673 740496 187449 495517 181868 595148 984874 517177 193125 39123 742816 63080 249646 503337 865979 381045 163 93661 41986 651282 180015 5057…
Output: 262467

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.