CT61362

The vials at Glowfen

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Aldo found an old ledger of vials in the observatory attic at the lantern district of Glowfen. 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 <= 2333; 0 <= a[i],x <= 1000000.

Example 1:

Input: 789 98832 315136 225674 720994 486094 84852 726070 109363 259479 201913 799653 937183 154600 69401 506641 234282 396678 147337 304703 503 104089 773535 74190 216190 880120 48835 776195 462130 16961 520801 325544 164709 30669 531616 921752 476319 237834 704887 620778 731781 49540 681411 324275 49794 81068 99409 507163 559956 800424 23920 75932 982084 682192 755443 659700 252681 949628 480430 849146 199589 485355 533218 814848 718274 480823 6673 521464 531575 784606 774711 478475 757144 124126 912837 598241 292069 753840 983245 414580 627940 913127 993738 300571 676049 413761 880925 225743 261965 29718 690214 17463 993342 373649 819088 328991 360886 487366 210032 40147 858149 695831 18499 458631 320133 986839 338438 727081 27858 789977 47608 140628 25319 384730 377802 638071 416583 131852 90…
Output: 151759

Example 2:

Input: 2100 1233 1080 999 559 1963 68 556 2053 1556 799 1054 1347 2056 865 1530 579 278 2058 1206 734 95 1028 1218 229 1365 1773 1927 679 29 704 428 1636 37 662 1753 344 553 941 1105 287 1717 1922 2020 266 21 1605 1752 1797 998 295 1683 680 1231 183 185 2022 793 683 58 779 1940 1132 2002 1676 1426 499 327 1441 270 39 698 1667 594 2026 393 1630 1 1996 1349 414 117 1675 1920 1680 1438 1999 1335 194 1113 1688 211 1102 708 842 786 608 374 2047 1493 617 879 657 1949 984 91 1687 1162 2010 351 156 2025 1247 928 658 1167 1487 789 638 271 318 111 1129 1679 1138 575 2043 833 1161 23 281 193 2006 549 180 1364 337 1716 1571 838 98 1827 1352 1926 120 1756 963 1780 1653 410 475 1547 988 208 1456 1881 2038 1660 2055 450 1355 1644 1847 882 831 1998 1041 33 1787 485 2068 1638 1182 1333 1449 1818 953 1294 2093 193…
Output: 1115131

Example 3:

Input: 2297 406304 42405 898410 734883 727757 59783 749102 982613 739090 109693 539938 262352 362523 961558 454378 58054 357931 607069 17337 626519 941297 177512 192115 564286 46387 338636 847031 463258 428410 332114 440919 115255 65143 473276 324264 126728 995157 518846 503939 372042 820862 140475 692709 25428 146000 496390 340089 364483 511951 561701 85195 161012 218556 924368 951838 553856 382944 122272 759992 962136 285460 956889 749582 167606 147651 692772 481512 659483 555228 437735 582964 386921 166924 630347 534518 413183 831012 842511 921047 527203 689901 705711 782006 90566 842495 654906 286056 435530 392932 855290 383423 144355 29004 553003 709101 366462 552454 618421 427580 351558 302323 934210 842576 552974 866832 445346 49591 872382 68379 556082 142555 314359 789468 919759 567304 76…
Output: 1295815

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The vials at Glowfen - MEDIUM Coding Problem | CodeTikki