CT64734

The Disorder Count of the Moonlit registers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Deep in the frontier camp of Duskwood, Fiora studies rows of registers entries. One clean number will settle the guild's oldest argument. 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 <= 2968; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 573 773595892 432008275 105519253 20720321 432135254 291457437 615271553 940445176 810217091 570456110 794534567 543400114 846122385 467952453 296694187 553303120 460708697 876262325 424634271 125489079 983798736 112127012 658856656 102521987 259198297 14952469 359717366 142772633 437528177 920525860 477090934 583160668 556146716 424070109 177641365 281462831 695027621 300054367 837947995 367892381 851439640 729270089 171363228 641415057 522455713 256322165 498147407 983604836 367454153 12963440 121999411 880157912 716144931 478977507 434527430 780974429 587185677 368238407 539140792 996963041 564409739 877419870 487609817 233137674 78547091 941464026 516335521 900622988 966857013 495417696 169341626 793054981 77849626 3955609 474735613 902128148 541485247 917714810 552354382 31126313 9775…
Output: 82990

Example 2:

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

Example 3:

Input: 214 471253455 -997539 406425771 690831753 419252747 483051365 70704127 567062416 880213162 672814295 707053409 129591302 638053896 980013152 464744555 949989982 892406243 902611439 286574844 343681808 471516318 712311728 760535487 909346406 199293936 761664964 205353203 916542569 169242043 67142576 336749592 604922913 796558552 846999184 165523487 592766795 187114289 749204637 854844219 930850700 606219720 102035082 847905654 697847638 617998083 672484471 506071397 806216154 317657836 630019804 642302492 351776239 296571016 428420164 132704377 95039444 704245254 905059036 71743316 826980640 625100641 189907114 748698730 692483676 553882085 519196591 872521000 82822023 815597263 929354989 902713596 894630351 457674061 122018960 358426354 238297823 98881535 820005517 388414587 690580660 2837…
Output: 11634

Constraints:

1 <= n <= 2968; -1000000 <= a[i],x <= 1000000000.

Loading...
Test Cases:No test cases
No test cases available.
The Disorder Count of the Moonlit registers - MEDIUM Coding Problem | CodeTikki