CT60017

Gail's Jade Ledger

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Deep in the smokehouses of Brineport, Gail studies rows of ledgers entries. One clean number will settle the guild's oldest argument. 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 <= 3832; 0 <= a[i],x <= 1000000.

Example 1:

Input: 2301 1829 836 2194 1037 2094 170 2218 862 404 1021 616 1876 867 1174 820 816 529 1590 664 814 576 208 832 1743 495 675 347 405 755 1891 1997 1783 2279 554 1331 1645 817 560 338 1927 2050 2181 1972 2268 1962 379 1321 1439 613 1094 10 135 1429 1460 27 2127 385 2282 763 768 1631 1469 441 659 1903 2118 7 332 275 496 2203 2064 466 155 118 1699 2034 290 1402 1268 1370 608 2137 1872 136 1779 724 1267 39 1263 75 2080 1154 1400 1069 1032 632 2044 2289 1594 229 941 1811 643 279 163 761 2019 1045 1860 137 989 1158 1655 149 1102 1723 1112 1179 1628 599 249 1560 2221 2244 859 544 639 849 1459 183 567 641 269 1700 1634 309 726 1714 2296 499 154 327 1949 176 411 876 636 237 502 815 1676 1013 173 990 1269 1978 179 1087 31 2150 489 1672 1942 2011 2102 801 1907 78 1799 2199 2166 533 979 316 1702 2284 2120 1…
Output: 1339297

Example 2:

Input: 2413 760910 602897 58394 327227 859641 650938 649386 67292 851439 976199 871396 903424 719441 593429 499460 810349 894434 952662 548218 824997 951373 226918 514464 477770 24811 342268 53545 88284 627170 757687 34018 21039 680812 915403 460345 456027 166300 620122 219688 925849 63338 242763 874264 255474 194496 482564 257493 933393 225821 625278 837282 815793 428525 14238 500851 298891 775952 657237 36309 686084 566844 433484 119898 205726 108360 468343 510804 755173 606855 860885 871636 787394 999106 83556 27416 706794 633652 702615 15694 492262 85927 450227 992814 10861 467005 385382 611252 929891 823613 86748 746403 152021 460712 787394 313603 416667 818621 462290 78270 24373 329445 969677 808259 593371 267168 940328 310046 362738 281408 265326 896233 566375 431798 884692 297840 450422 5…
Output: 1488744

Example 3:

Input: 2150 770 918 1738 245 1893 2131 565 884 1268 1440 689 391 1493 552 959 997 2097 1063 418 2063 691 470 474 1566 39 166 378 191 639 179 1093 865 1458 1193 139 908 864 515 1746 1519 802 2025 655 188 556 1343 1674 591 497 1431 23 1878 464 1611 134 666 480 731 122 2026 1706 1719 1718 1175 1676 842 2034 118 636 1073 583 1605 648 110 220 385 1385 1955 229 1578 1617 1318 1153 2053 1923 248 1422 1630 449 1019 682 2052 1147 1672 1575 421 807 1352 596 511 1904 218 1568 2087 2089 456 549 1339 355 944 1015 1572 620 212 1930 1103 1031 2104 116 2007 1577 159 285 1266 193 57 678 28 1206 492 1065 375 2109 699 942 424 1104 1476 1247 902 469 135 104 1887 1861 723 397 1461 1410 837 352 571 1056 658 962 1884 2055 2106 1016 490 4 1289 854 877 870 176 2121 1507 2128 706 138 937 612 24 832 1439 1011 810 85 1862 1…
Output: 1140445

Constraints:

1 <= n <= 3832; 0 <= a[i],x <= 1000000.

Loading...
Test Cases:No test cases
No test cases available.
Gail's Jade Ledger - MEDIUM Coding Problem | CodeTikki