CT65348

The registers at Cascade Vale

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Morning light hits the ribbon falls of Cascade Vale as Blythe 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 <= 3333; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 2405 810373178 414049484 293053708 669321166 713205880 867118414 360209479 174453949 103891456 388557089 299787639 565319145 472578882 107139862 567013127 502253547 821286212 852677933 78442049 154294897 783903250 977242158 849064529 781068944 31186236 398340123 575170970 688570778 673936434 774211839 467969075 413798050 615495153 429311715 931038770 270163146 115093030 552072940 806016994 740123067 239801053 553946930 117817186 600242170 941930682 982689525 86875498 706398130 119920719 397018831 798626729 727679928 306146990 279176769 329439876 893323790 218189182 425933381 75388943 897233482 928981566 370992086 75664360 514187716 579838339 989925371 763966254 609584793 240832860 427746550 119523779 886968168 807796948 239056313 339094686 579154875 336225645 227191819 311245247 169451054 …
Output: 1457743

Example 2:

Input: 2454 101 2333 1496 1457 1753 1432 1110 1946 1176 635 960 1156 698 1491 227 1187 1028 716 2027 85 1114 2337 1564 805 773 259 68 2006 1327 943 1285 1638 1403 1909 2300 300 884 1750 1985 467 478 672 714 1029 1913 325 56 1166 1547 2437 268 1584 1322 2161 727 1221 457 1215 1212 966 1479 1514 2356 292 663 42 636 941 1243 2054 1247 1184 115 1417 2181 184 1036 395 1346 473 1787 73 886 526 2397 1720 2335 2381 1801 539 2075 593 793 2340 907 1249 1405 2124 2345 1854 276 1710 1871 734 2120 909 544 1610 1350 624 1139 31 1466 1856 30 2384 1282 959 2100 22 678 936 1501 1259 768 1349 2276 149 1317 1292 1843 843 2391 783 1949 1355 1519 1760 23 1400 788 518 2285 50 2222 2249 2159 1453 2434 712 1395 308 1693 2022 26 2425 1935 630 2173 2071 1338 2257 1159 1941 546 339 2388 0 154 2141 2199 1781 1561 1815 726 1…
Output: 1493829

Example 3:

Input: 2029 655 541 2023 1272 46 229 1456 1756 956 1630 1196 873 1553 1969 845 251 1025 654 1950 754 508 1784 122 1229 1291 237 62 1277 1732 1340 354 1848 853 1506 23 486 1793 12 1512 2026 324 1827 1799 1434 1973 186 1878 439 2015 1446 690 1633 317 1190 583 1873 736 855 600 946 1895 505 329 1575 803 326 83 409 67 1893 648 1619 1474 1418 914 510 133 533 1746 1990 1677 1766 1862 193 689 1342 1801 1880 1916 1542 182 1465 877 357 827 394 814 64 432 28 1622 1117 179 769 843 1647 297 888 96 656 970 429 835 1577 149 338 73 1824 647 909 862 1411 1675 1135 1395 1639 819 919 384 2003 1798 1724 1136 1319 260 488 637 1369 949 792 1325 1733 190 639 1489 1517 683 546 1753 1689 528 764 753 191 158 253 699 1278 711 1989 272 1208 1365 738 255 433 1140 559 773 1073 931 1224 1398 1221 619 1855 1635 1394 624 760 443…
Output: 1013793

Constraints:

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

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