CT57443

Bram's Ledger of weights

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Bram runs the boathouse at the rook towers of Chessfield. Today the books show a list of weights, and the numbers must be worked out before sundown. 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 <= 2891; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 65 21 34 64 41 26 35 32 47 16 22 60 5 25 58 4 37 56 49 38 12 50 51 59 9 0 15 18 53 48 27 7 11 17 31 46 57 10 24 19 6 29 61 44 54 36 33 2 28 52 14 45 20 43 42 8 13 40 62 55 63 30 1 3 23 39
Output: 1077

Example 2:

Input: 2438 834698838 285549945 197756638 299427436 526460492 660044107 991022734 436250700 470006976 977808560 617981465 238886207 769221814 279064420 863679073 47848955 991478330 947175396 582816256 957621529 11203520 241331361 46588754 945652332 540668466 65479048 699050972 653488566 98085326 304665856 892726897 328656735 293402751 982117380 481928122 295250328 659685141 879155321 590957846 618241101 186036612 409628713 815414538 631855328 532603298 754948120 909472317 420819996 723939641 337715684 807379584 578126437 818048064 128029408 723342414 16683595 720256443 278432486 471561100 816298843 817613996 781629371 791372870 243449476 399007594 679085782 721396138 532045904 804666856 780125411 379103973 979863781 804697774 405586690 239559441 7748191 264539453 698532298 678670520 779134337 255…
Output: 1490382

Example 3:

Input: 2282 804 1334 1543 200 196 1370 1140 83 1027 2076 1963 1605 1889 2154 677 1253 963 659 2125 1747 975 2038 24 1683 214 1936 999 1784 363 1801 158 409 481 1295 2277 595 1738 1058 1152 829 920 1849 1218 1625 2133 1059 1257 2084 1429 905 534 1031 414 1995 1442 1421 1460 943 638 2269 1045 639 1878 2113 771 761 435 45 1756 817 1535 693 1275 952 328 1892 1052 614 1619 864 1653 2128 667 1772 599 1261 76 465 176 222 2035 338 853 1714 2206 1235 1912 1505 1787 2186 1233 1854 1791 1622 2152 726 2164 1852 1418 469 2060 1009 787 1729 849 1092 221 715 664 940 357 53 194 2209 27 2184 1192 970 353 1069 1420 408 2085 184 2158 736 290 31 1472 199 2138 342 894 1201 1056 1630 1549 54 1590 807 333 1292 1269 2145 1413 1715 1939 528 1616 1241 251 1911 1990 517 2280 547 510 247 1271 1914 1669 1184 997 131 957 107 …
Output: 1315492

Constraints:

1 <= n <= 2891; 0 <= a[i],x <= 1000000000.

Loading...
Test Cases:No test cases
No test cases available.
Bram's Ledger of weights - MEDIUM Coding Problem | CodeTikki