CT62695

Emir Counts the vials

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Emir found an old ledger of vials in the cooperage attic at the observatory of Starfall. 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 <= 3727; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 1893 1694 1345 948 1843 159 1088 1564 655 1817 1004 1638 1669 1022 678 547 1156 1461 1145 1491 298 229 1717 34 1065 396 1331 535 963 693 891 914 1768 544 1400 175 919 934 1556 390 475 1664 1581 309 1464 1588 1557 674 703 488 1737 1560 1092 1085 1280 160 821 1850 1777 1544 364 1661 1409 810 1795 9 1358 656 580 716 112 1825 1178 607 916 1707 1210 1048 336 1028 870 1858 339 272 356 1877 1392 1629 43 1233 1540 342 1804 687 99 1327 1426 1322 1644 1662 1040 424 1688 1420 302 197 1488 522 1637 297 441 528 1730 464 904 165 1068 747 1131 1007 1691 277 38 524 1008 1163 1293 307 1240 680 926 166 1552 1765 82 1741 226 1514 574 485 143 1336 536 961 1248 1318 1238 1512 608 1216 1402 1395 472 770 704 1505 590 1769 1533 784 1207 1879 1351 458 1736 654 548 1477 1698 1722 1538 545 268 127 1609 1743 513 1237…
Output: 925598

Example 2:

Input: 2629 555 1420 1278 1332 1145 2360 1529 135 620 1736 886 1510 485 164 37 2284 235 1547 2304 276 2297 1960 1313 1520 2272 1943 1137 339 1175 1153 1268 2019 2114 593 499 1159 387 1686 1813 2045 668 1835 744 365 1115 418 490 226 1600 642 1103 223 1413 2367 2597 2334 1162 45 1640 35 781 392 2496 1113 993 965 421 587 1073 49 736 1065 1616 111 1550 1992 34 595 1388 2494 1014 1750 2616 149 2516 1526 2509 1778 1095 153 1392 626 789 2582 1138 689 2172 2150 203 1200 1241 2527 2570 1357 859 743 700 1895 2099 904 801 166 674 33 1913 831 1851 314 2329 2204 2168 412 2465 190 2429 2503 1152 1552 2612 2431 1817 1820 945 2040 182 1315 428 685 2580 1488 1567 2472 305 1244 464 1085 29 2147 497 774 885 1322 1154 2373 1872 748 2252 930 1240 2440 1148 2240 994 1792 2445 215 161 1572 273 1928 1035 1884 1994 877 2…
Output: 1731340

Example 3:

Input: 3487 817444 -101858 -600666 701574 400889 -628817 -956216 -594399 388142 -912000 -250778 -758924 -24446 726188 -889005 374059 -317736 -949454 -125838 -383104 604422 -38576 463571 584761 343131 -750347 -443373 -361653 -823836 57959 777978 568666 167134 510168 312152 46093 760562 -751970 -954797 -440096 568519 -535814 -861661 -678485 -948117 -771663 -829605 815723 227606 -997070 -33632 -93276 -78814 -671500 623438 702635 679215 920949 4139 665453 731565 193213 -36583 192110 -749476 -620248 1054 403141 -414139 838013 790045 -265609 -943457 -334634 104747 -244854 -4337 462490 536451 -50679 -952835 -353888 35535 -737182 259643 691825 883586 552010 474493 424524 536882 777346 -767328 655405 203491 -296544 -552622 -818851 -439270 -440731 -552164 -97815 310697 -406004 -421641 291777 472727 956993 …
Output: 3050736

Constraints:

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

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