CT61693

Piper's Disorder Count Ledger

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the mushroom groves of Fungaldeep, Piper records each vials in a worn leather ledger. The guild wants answers, not guesses. 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 <= 3539; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 2225 2088 1175 1939 1635 163 205 2051 1356 713 1075 1493 1996 1410 1387 575 175 255 873 806 5 2085 1117 543 1590 968 393 244 2189 1395 1562 530 65 1437 705 1296 152 400 947 1067 228 2196 2082 1771 779 1856 1857 343 1496 2147 1879 1049 1933 116 1952 622 1669 2058 1610 1237 1034 2027 1704 415 110 420 198 61 1989 1819 1633 1979 1722 1307 1518 1990 1811 2164 691 574 1202 1025 1158 2049 1323 2057 68 1240 1519 955 1401 326 1624 546 693 1002 630 1956 815 1311 318 162 242 11 2188 551 1482 2207 1360 2019 410 1108 2048 1868 128 1582 1854 516 1894 139 1042 605 312 991 451 216 179 664 857 2152 1549 1083 466 2211 1498 436 1970 1373 224 1761 192 1564 1796 1528 645 1653 891 1491 1695 267 627 376 1488 2090 1009 909 515 795 1366 1229 240 703 1741 2215 82 1839 2190 184 433 1357 1567 200 261 491 0 534 1841 2…
Output: 1233270

Example 2:

Input: 2504 694170 610950 204517 291486 -111749 -91116 237309 93943 -966384 810102 574192 -35097 588036 976436 435370 -181843 735849 379746 -210560 -974506 -615663 -809230 -468638 884702 772387 -293764 355593 -321311 -178117 -326008 -49117 -115624 -634117 -946343 856614 34836 482648 188550 347040 259786 204268 701080 177872 434670 -126795 71403 -896568 223660 689551 -263926 -710273 343760 315631 -4598 885437 -185592 780886 159865 -649255 -127625 -399038 -585912 664692 -295340 169720 510818 -763478 -200641 4846 -940715 -720590 -497305 880002 427085 -519123 -268889 72527 621252 -552850 -739828 863749 584038 153296 -876192 -533788 -185817 -518939 -818598 995458 -655209 -862453 444935 -242504 -40801 -105042 857190 -312536 32950 -959778 565285 145127 508560 -478595 867398 -894763 -494998 79482 376340 …
Output: 1536169

Example 3:

Input: 3374 2070 2185 352 1054 3257 1786 80 3307 2775 1874 1184 3289 3208 301 1320 2051 789 2448 2830 2782 2772 54 1894 3069 1535 582 685 922 2640 652 1565 1717 3204 2676 1207 2084 1275 1183 924 927 732 2413 3114 1074 169 1415 2612 664 210 3244 818 819 3178 3210 1380 2976 19 2183 2983 1839 558 2230 3001 273 3185 489 1953 3171 1964 1702 1641 295 2325 1120 1089 764 1808 2387 3353 2065 1630 3238 1311 2158 84 957 2723 1126 758 2179 1872 743 706 3137 3356 2803 633 1001 416 1907 1162 3092 1521 2452 720 2228 2483 731 435 144 886 569 1167 2683 2549 93 291 1113 1042 78 208 2553 270 1266 3144 275 177 1574 1618 964 2524 1625 2771 2556 108 274 119 3104 695 1686 2691 883 188 2435 2655 2284 762 2509 3126 311 2203 2003 1913 2565 1479 807 554 313 276 1854 2845 959 580 2087 2597 1593 2440 1271 2409 2692 2113 1419…
Output: 2862642

Constraints:

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

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