CT61873

The Disorder Count Beneath Amberplain

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Tinker the store warden watches over the savanna camp of Amberplain's stores of vials. A careful computation stands between order and chaos. 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 <= 1931; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 110 637895967 123685990 929788160 523365397 73065323 214865856 730890445 446880015 464240603 482217690 627823911 921397159 200374421 187459875 40135738 392661972 816179568 755877452 736564806 382178308 466481609 678050677 717170296 529047355 145386948 530334839 537368708 279563503 424742864 487507149 27251042 173494328 636491148 919371128 470852032 300001852 631543421 165487886 320167033 802438049 603545933 212079047 347090548 19545766 258632339 268300288 40836739 222505738 575236407 359342825 493940786 96313939 805503735 534872821 152195076 739146259 973383440 216977576 944599041 912582219 788863995 301918277 298940771 212884729 741957561 750559547 16906783 902206254 391186135 114358612 903013391 222094262 36947966 427916837 133114000 448866103 653687425 566382268 917596062 286052437 3408…
Output: 2956

Example 2:

Input: 261 623385472 259800312 691286665 716062131 9623417 490052796 640768413 639598975 437558507 287562357 583664538 518829567 815727673 258804901 457460359 212939956 763693017 517556901 425519031 646469858 486302481 972623266 890144889 6848147 172782318 264543194 595903685 856353805 272282274 88401516 519607552 464193769 319216510 968669831 155640380 180450533 74644252 184682262 834033359 637922663 875878375 514862369 516067478 338507724 320684130 131731081 497569885 72029474 656775673 607576515 388382550 497845911 745875644 24438866 54938966 857662557 507658731 150065681 339516159 543817835 656896797 119730157 49406254 165977643 28816865 931656727 999489091 71088090 625090083 351390769 222908537 935987044 29908848 734591615 884905256 69646255 443354818 582683671 981125646 86942331 816808045 9…
Output: 16883

Example 3:

Input: 102 90 72 30 31 4 100 8 68 69 101 34 64 39 54 11 61 20 91 52 63 77 49 83 48 88 3 60 46 24 59 16 36 62 55 99 43 79 0 58 87 66 25 70 76 94 98 93 81 33 37 7 44 14 29 57 23 5 92 40 28 21 17 12 89 41 27 38 32 71 65 26 84 82 67 1 80 47 15 19 10 51 86 74 95 97 45 35 50 6 2 18 22 53 9 13 85 78 73 42 56 75 96
Output: 2705

Constraints:

1 <= n <= 1931; 0 <= a[i],x <= 1000000000.

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