CT63326

The Rustic ledgers of Innkeeper

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The council of the otter slides of Sleekwater pays by the answer, and Innkeeper intends to earn it. First: the full register of ledgers. 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 <= 3079; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 2438 -346930 -129745 -378251 642076 -199121 -861957 59929 540680 -630527 554504 -744780 410180 926354 731838 -671097 -455010 431338 976211 -179044 -717219 431874 -484052 -149564 -614037 -213890 836149 559725 -450084 750206 -564321 899814 -283153 254664 269732 85229 -129225 -260167 26908 -668061 63754 733630 758558 942310 -671543 -375976 433064 -268227 909933 173819 250991 -61559 231346 977734 -733403 927748 9728 -970823 539193 456316 -6402 624908 -895062 -771470 696817 243980 -505279 -742336 -703337 356383 980072 908624 -865814 -634093 564096 709684 95 868660 -534552 318383 -402706 886635 -678570 -521826 -593685 209419 683630 736673 820552 -961788 113465 8045 335158 518202 -713322 -814058 66114 984555 -411189 39292 243695 253432 -413590 -39890 259956 -308538 -230529 -743250 142629 619086 -…
Output: 1457670

Example 2:

Input: 871 -601211 268697 -172927 -278153 -193164 181965 -392450 497856 -873047 -848530 789009 -144430 568336 -1902 356613 844614 561183 -646642 685028 -961091 915479 -566397 -646899 510025 -993978 -249376 94318 -642337 -887384 738346 -129733 403103 278120 415921 579595 -773166 102703 -914357 999106 -238931 63715 -546660 963520 370954 724757 577898 -78177 989585 -554388 -494207 472692 -887670 -339363 -337366 617019 481791 -233667 -992028 -534218 226624 -426810 887725 -206578 394764 289062 -505832 201522 -347997 -266880 -624765 -426564 613961 809587 501659 235741 146698 -649768 -975744 206085 22548 -957092 811598 191040 642858 -104060 -4531 -68722 524520 -723745 -879830 -520391 -262731 56405 950953 -23754 -63937 -676923 -559493 -712327 -913806 -727656 593454 -737545 -383548 454955 -785442 382588 -…
Output: 187476

Example 3:

Input: 2955 514 2085 2284 818 2913 1665 832 1445 2081 7 2839 2188 2621 1738 2131 2411 391 2440 1037 1410 2373 1731 68 1617 1826 783 561 240 650 1484 1695 1761 77 758 1709 1217 1007 2006 1652 2690 530 869 1210 439 2164 106 1411 287 1779 2023 541 2804 2066 2809 656 911 1370 641 1277 14 2460 1223 1638 159 317 684 2502 2613 2838 945 1908 868 954 527 1416 397 1601 2407 740 1859 2701 2089 2139 1719 1042 1936 1017 1158 2711 1489 94 2630 1043 1386 1022 417 2891 1458 747 842 2816 748 233 1146 2172 2274 2919 1110 2318 168 722 1328 1922 680 225 79 1155 2786 1166 329 2820 2636 713 1492 2086 2308 407 291 2380 279 668 1468 716 1010 1587 2120 197 2075 1882 1008 2403 289 827 957 2319 2873 435 607 494 2771 2594 509 64 33 355 2193 2288 1100 2554 2250 1242 1931 2378 2676 2903 80 2437 1321 1968 188 2238 1298 2026 41…
Output: 2179765

Constraints:

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

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