CT47112

The Ember Disorder Count

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Cyrus found an old ledger of shelves in the greenhouse attic at the salmon ladder of Rushing Falls. The margin notes pose a precise question. 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 <= 3992; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 2130 1471 1248 2110 1724 1469 1842 827 1301 1395 829 1545 1493 1990 2094 814 1864 1086 1461 629 900 1110 235 1057 1622 297 913 1711 1370 1084 701 624 1969 1230 123 1550 1739 173 1514 1290 1731 1207 1877 1410 599 940 1954 1544 2034 1650 1548 797 350 406 1328 784 2109 614 1575 591 1329 167 1646 842 2106 220 1902 1826 755 414 1214 1179 515 1569 1686 1939 1527 1872 1222 780 564 407 1386 1043 1162 285 2043 1998 101 1367 1923 1704 732 174 189 382 1443 1624 50 1095 237 434 714 1418 1136 1129 1361 1100 662 1640 1363 1275 348 2017 523 1362 1194 1848 1734 1029 223 972 1429 2050 228 510 289 1052 1623 664 1106 1170 694 950 1404 1929 982 213 2008 1782 764 929 325 271 1041 1478 1467 1182 1288 1642 1564 481 906 1186 16 241 440 1981 361 639 1843 1516 1434 2071 881 2064 1393 451 291 200 1196 1788 1263 1685…
Output: 1156619

Example 2:

Input: 321 995088194 402990101 100943389 256552728 500727054 825769898 222164021 174314760 810473286 257401653 617781309 820877939 380837759 83769737 703718741 273825041 42567425 983007410 866033529 905440949 572505858 351985480 69661876 871894398 403879887 521025936 196989373 214806659 258568832 517742462 27771381 123360917 877785765 352519878 964532816 80003226 438960744 714384933 39609188 739991981 686476635 285541909 690570155 705365177 986519124 563328521 411638000 563460957 748195330 998849424 79627211 723334731 759801321 920306586 20923577 484162141 719703680 952557995 209013302 82174922 925888809 441906395 913310769 722372648 528840616 89577043 3109047 767332214 257453148 535803844 205419233 15361756 865835595 66439149 825400506 701223210 984219205 288500274 343082684 868879190 361177404 …
Output: 26831

Example 3:

Input: 1900 337 1652 1760 1779 719 1283 484 194 519 961 763 419 441 518 1875 1783 751 773 1711 1807 334 1026 226 392 408 485 431 1429 809 831 1431 1028 722 770 1081 1156 1549 744 1012 1792 1325 1005 786 1134 1822 1163 1370 121 268 1162 284 1461 1588 1540 1832 4 338 900 18 55 64 774 564 172 62 717 1297 1417 321 665 20 1495 1038 166 625 481 863 669 333 1144 8 1642 444 1896 584 1572 864 941 640 1505 646 1195 577 27 142 350 1112 1192 1439 1352 1039 1436 1613 379 410 1025 1712 131 839 190 668 1459 492 59 800 1445 870 1577 1791 1362 1716 1406 873 289 462 369 439 1827 496 823 1204 618 221 378 1322 1705 1667 42 906 1765 1573 1155 994 1556 856 1824 56 582 498 1419 259 1250 1880 26 1349 1018 1338 921 1557 603 1328 1750 1029 208 801 1295 862 393 1110 837 1600 1504 1181 614 1806 405 976 903 1850 385 250 711 …
Output: 911350

Constraints:

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

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