CT52593

Ojas's Sterling registers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morning light hits the ferry landing of Crosswater as Ojas unrolls the day's manifest of registers. The tally will decide the next shipment. 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 <= 3271; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 3114 852723 564815 -631881 906644 -143302 452123 -230915 -774197 -264189 -903850 861421 -235290 -688199 237540 -675982 -19896 -509339 -902130 -456594 -667620 24362 -154687 -723890 -165819 430372 -514036 543145 23654 31065 329627 471599 -516661 354514 480434 859386 -561238 -664893 713929 487933 645510 578105 255175 -711195 391437 -413214 889670 -530542 -132412 717792 -793418 -83224 -831350 -831480 541178 -769000 -785393 68724 294342 -605295 -681937 -793211 -686117 -25110 -990845 -366330 517968 -212060 -404322 -729267 -671521 -711875 -248037 675624 -675181 40669 561232 337381 47644 -691311 992222 -520254 -425972 825113 -125270 898414 495762 -748055 139629 845947 227260 -331685 -517975 -434851 -929568 976029 -612029 494075 -481606 441505 -397464 732693 -418035 75257 434257 763063 -318146 3017…
Output: 2396962

Example 2:

Input: 2522 -264740 436737 293346 671912 -390807 -751833 743545 525557 791615 517247 910015 416747 44527 886148 -935527 458757 196262 -906827 87328 705466 -168029 432819 -978724 -432680 -5718 -809506 392396 806134 -832868 -646915 -831826 321309 290118 595988 846935 664678 -717342 -706863 304906 901437 -937643 -332199 -681173 -965702 -346092 488925 9153 149237 905938 -6183 142790 247402 -63853 -562736 317572 -366845 427540 -565356 506172 196417 316883 -211725 497021 187748 177609 953484 67041 -983811 -176462 -391422 -65163 -170312 -90369 -905293 -67125 189051 -2299 665862 520502 -65184 -960708 951419 122073 -676604 -996362 -499139 -852860 946325 -144255 946098 -111508 -509545 493136 599629 -97212 712751 -327481 -44220 -546714 317967 623165 -304451 -417029 772547 39345 -557792 266869 -232703 -84912…
Output: 1595438

Example 3:

Input: 2823 2005 1766 2519 965 1409 2176 1439 2795 1919 927 2786 2674 1815 2316 2130 1115 2037 1503 2163 2121 1468 1079 1448 705 614 1995 2004 1812 2169 2193 333 686 245 1639 1669 852 1838 2464 1936 995 789 2051 1492 981 1742 1201 1654 1210 2284 571 946 380 273 2147 2241 1092 1522 1770 2797 1795 1620 1868 2434 100 78 13 96 2329 1196 163 1067 2777 2766 1656 1260 1054 22 246 287 2689 2007 780 1465 2356 1864 616 989 1128 1220 2010 1783 1859 262 1122 2582 1601 1874 2380 983 1274 1117 1778 2249 401 2215 1891 2302 23 1372 1846 1248 2505 277 860 1741 2733 2531 1830 450 663 2319 2423 283 1125 1863 1194 1232 1156 1494 710 377 109 1561 1183 2611 2498 284 1161 76 368 305 544 2264 1343 1910 269 937 1867 1304 1521 231 527 291 2675 1884 594 801 2397 923 2394 156 2209 1724 2238 792 1142 2534 1350 2647 267 165 1…
Output: 1994690

Constraints:

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

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