CT50647

The Ruby Disorder Count

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the mushroom groves of Fungaldeep. Clerk spreads the registers records across the table and picks up a sharp pencil. 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 <= 3813; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 3774 329703 -493562 329687 -421096 951715 44768 -219919 -804321 -394061 604042 -544001 -575328 358568 727519 -981552 -583017 959605 425175 638905 64324 -769958 110380 -533075 -619234 -330862 -741813 256413 251932 318634 -33784 -385293 796597 713435 903529 -592624 -666702 -620032 855478 -838205 505043 -259225 204711 -859687 -756382 241875 29502 -743406 714660 873402 -415526 417664 -430213 -611837 964558 763060 673716 -953652 -681457 513744 -841640 -984310 421036 -267071 -887227 -644224 659530 -853249 975786 -13201 -262384 248698 33517 -934925 -791569 25990 -227012 -244608 845792 -816174 -720677 -736932 -78591 766389 184750 427037 -953719 473478 106199 -584928 -810291 -80706 -470882 -528475 558585 494721 -457598 303083 495881 -499877 -723553 -579400 -666695 -40560 -471305 464182 504218 -6132…
Output: 3515843

Example 2:

Input: 1323 -979796 550818 220972 820475 -636836 -343551 602555 -714810 114858 -162878 366300 -939411 382125 -218206 727018 902417 -311315 520647 589679 -797267 -491726 278931 -181943 497964 -315972 -213704 -196035 -230667 -384022 -18673 126078 89813 -575815 -121030 156337 -949090 -417820 670081 -234102 31805 964191 -62170 700251 -32796 122533 824561 441566 -863735 871788 216038 -886150 699178 -383573 93152 614752 534331 326431 728217 563260 -871314 -312335 -254239 -289794 -292310 927439 -963498 513684 182717 847970 103254 -156957 252330 993453 347609 -977226 38716 -244554 97297 231516 -987769 -158543 -547130 750915 -581161 308903 -195894 300972 -854880 -755083 598534 954098 539945 -20047 243082 79445 -466080 -57607 132456 -228043 -962717 259654 -336691 -888414 -114552 905660 -76346 -329802 -7864…
Output: 420483

Example 3:

Input: 2374 2286 574 1484 1254 2278 1590 1347 1811 1281 1264 1493 413 2055 2005 279 483 1688 1479 2134 323 437 792 2027 1478 1461 727 979 1608 2354 1749 1989 1992 293 2074 927 1147 320 1580 2222 1589 1322 1216 463 1530 1012 1129 2270 1170 1362 1138 44 346 138 2295 977 1946 1686 2145 1729 1223 1566 641 937 147 395 2144 1449 1236 1606 1342 1571 1565 383 2042 1979 864 1864 1008 333 85 342 582 541 885 1785 171 231 292 1689 1850 1554 881 1323 1028 957 341 1597 768 2245 1263 930 2178 1432 712 1158 2344 624 1768 778 1718 2078 1804 591 1466 1985 1877 872 2092 2333 344 1579 1965 1577 316 241 343 267 844 306 1854 968 820 1951 75 242 548 2039 1625 867 941 81 2300 952 1713 325 2012 1986 1290 1055 2146 32 240 1450 482 1994 1570 997 948 1865 478 2072 435 1694 265 1938 357 664 604 1321 1797 1628 1111 2267 895 2…
Output: 1425244

Constraints:

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

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