CT62163

The Driftwood Disorder Count

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Envoy the quartermaster watches over the quays of Driftwood's stores of ledgers. 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 <= 3800; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 1603 -885620 -943642 352710 -931106 -573700 305426 686577 590685 -326255 -55820 -365232 -165207 -252414 183853 392893 -489746 -652417 -736760 -282175 855653 363149 -155853 -44882 432871 799122 109319 -427968 990524 33763 981605 71064 -237098 -320920 -215891 -632755 -565101 -488632 -976067 -475622 566274 -584103 -827 856639 -659056 -510674 -276318 338295 63161 -254079 -388476 134870 -341705 -17449 -117885 144504 -380242 929344 644055 -210025 609884 -488950 -644342 -97261 -839138 403044 -247270 832992 249093 483503 996130 -293204 -61105 103503 86560 893318 -895308 -47975 886201 -141544 -256273 764581 124118 -963550 238010 875822 -397617 -305889 -684197 218913 857757 490353 -537825 -671441 -350069 -688302 -831793 466574 -948995 587694 -301397 -499642 885250 -138753 593680 -274324 718209 32521…
Output: 633022

Example 2:

Input: 1153 -383432 -121742 400351 767978 478570 -401398 -82248 -363271 -322307 361775 565655 549715 -479 447705 319387 -464949 855108 318405 342809 -935706 895899 342392 -317220 -137957 -424605 95729 25904 -888113 -450655 -30227 527991 120445 -630022 -971861 -290149 -896837 -97548 -951667 426965 -751302 -838479 285854 -163496 -553969 -799143 766021 453619 -465658 75851 -107760 349471 898372 -569392 984173 -571964 -776077 -263844 671612 -384810 -659500 -57405 561802 140543 -603901 604489 -828253 330385 -284170 461864 -245818 289943 -478214 -888243 605950 88502 -860206 97036 -206660 -394251 -428905 360993 -744972 -362626 920083 135905 753219 -763721 414016 -276208 177887 557090 329985 -420913 -572985 -969086 743764 -342730 890169 350022 472471 510242 -389824 -672433 130658 -92078 -407459 -592271 -…
Output: 320304

Example 3:

Input: 2711 732 481 350 1812 1106 1989 946 2663 2229 2081 1701 1934 965 319 77 2303 850 144 1753 892 108 1491 2586 2640 595 1408 1017 168 969 1091 1905 2419 395 1985 317 2579 2151 2446 504 1442 2278 651 56 1145 1668 1313 1359 1585 2592 571 1290 2296 2673 1506 905 690 1413 1671 349 316 610 615 2232 745 613 811 916 1146 678 2405 2477 753 501 2082 196 2069 826 2695 1480 1908 1046 1750 2043 1895 2268 142 386 2542 1181 48 2539 217 1610 1163 267 2644 883 2231 1492 1298 1291 2111 1496 1837 1370 809 9 207 2088 2629 1473 625 2196 743 2242 2147 67 2277 1009 2632 2421 2659 2087 2540 145 1510 2442 311 2313 2079 597 1850 2216 54 445 43 921 1918 1682 837 372 2479 2314 444 2233 2227 712 576 775 2510 932 2450 824 1647 1579 1707 2555 80 169 1873 1390 64 701 1341 755 1233 751 898 1439 521 2002 776 2325 2487 2276 2…
Output: 1830146

Constraints:

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

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