CT39512

The Disorder Count of Skyharbor

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The accountant Galen has been asked to prepare the expedition manifest. On the desk lies a long table of ledgers readings. 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 <= 3045; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 1932 45720583 886826353 703612727 196396914 438103685 27325271 321706177 449925273 263948809 397491864 625700075 764090197 91497001 823292920 897752676 282165529 950942808 633807500 703330890 77135693 44646685 338063820 156601647 288393613 888673476 311086034 557858253 513198960 243021008 70669094 433974329 261806330 496518046 888633818 253165598 749912465 155492019 754200492 176492745 806547686 728742931 649836444 508152933 508726422 65001231 910253159 145970327 877962733 605900200 743287146 557923981 68026712 896712884 566841814 238110588 763073286 106578414 989022020 580780684 420093361 607241507 929812114 820763441 196509838 126964597 952541348 50810297 358656140 948523846 924941766 818819973 325945151 570252942 823802205 854094717 422677705 903695312 658062003 987876541 731558477 5061…
Output: 931152

Example 2:

Input: 1340 395964725 769283103 229559631 568327330 38810002 13301119 577745727 324110718 997478473 212299475 131266578 717304977 61758712 259076810 880017963 847618218 771743091 507500209 202350848 57420390 813282631 471062192 522678810 671759794 192319651 721829951 185409102 539777886 976200000 322099764 790663273 379112645 971525726 504191751 695287250 464443205 938309434 370818250 483465561 868136048 887179307 363497675 627339024 368371164 389256260 49780599 466050176 759382594 442234744 301030193 520467265 476115543 212467763 958420793 105075061 228746804 837153177 56905122 892081369 354285706 503265884 743156698 877671993 141697953 898364499 541618792 625134935 653419783 10759627 559383713 903189331 25306217 111593159 356616391 959137632 315640528 41333793 437216098 95443014 577689069 44305…
Output: 448501

Example 3:

Input: 2088 947 795 1636 691 1101 1786 1947 1227 329 1390 1791 1925 2085 806 1967 991 459 1921 526 1082 212 996 1711 1875 435 527 1655 1968 1679 1837 2050 1870 1166 1407 879 158 1987 515 1854 772 22 240 782 1923 1442 238 979 1962 1795 130 1933 1673 474 1573 475 873 1279 1313 235 1886 808 1419 1030 1375 108 643 1197 79 424 665 737 340 1016 1078 1114 1157 283 1413 1846 1487 834 1566 798 101 267 1348 1171 418 1216 749 705 385 716 0 891 630 154 176 627 1252 789 1775 972 366 757 1478 1582 341 1811 1512 1178 1385 999 768 1747 123 220 781 122 47 256 1633 783 593 840 935 302 591 1598 2008 1124 291 1524 1436 1276 1942 892 1746 1661 610 914 1434 467 1189 402 759 966 2011 936 1892 1867 262 813 321 1761 1849 671 482 837 1648 1600 1253 7 980 48 1677 659 511 2080 1308 1961 810 554 790 1527 1570 754 1398 743 52…
Output: 1099556

Constraints:

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

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