CT64101

The Gilded Disorder Count

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Peddler runs the greenhouse at the temple city of Sunspire. Today the books show a list of crates, and the numbers must be worked out before sundown. 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 <= 2442; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 1144 830 1143 867 846 422 376 955 382 639 399 334 849 129 911 295 445 802 322 661 35 581 1059 550 695 894 541 701 492 833 432 1022 326 857 50 31 929 286 233 855 364 234 359 385 1093 775 1106 651 401 837 866 459 161 391 1102 92 141 812 495 363 649 951 868 108 335 1084 1035 350 73 487 707 591 457 134 577 210 142 262 888 1085 24 713 1061 355 450 225 313 13 632 219 67 816 563 546 882 1088 287 764 497 708 1002 677 644 248 776 749 1015 40 175 115 845 712 149 329 299 64 126 501 906 538 284 178 1027 456 177 380 976 753 586 11 763 575 259 532 486 824 1087 665 98 147 916 580 1070 566 352 4 755 203 160 1051 805 700 389 986 646 890 621 437 770 736 202 1020 291 70 730 819 184 908 971 116 12 926 321 693 154 582 310 124 269 1048 83 975 881 594 892 798 957 463 615 1100 482 216 634 191 331 252 584 340 921 …
Output: 315652

Example 2:

Input: 1956 1459 1007 1347 116 1018 1809 1868 434 1225 1348 1110 460 880 1608 1062 1352 41 527 761 1466 367 811 520 258 491 1146 1685 15 1104 455 563 518 1386 1826 157 762 36 375 899 704 1844 1686 238 1077 908 1862 1907 251 671 54 1642 1510 402 327 1506 1834 1610 138 525 214 1022 1529 1048 800 359 874 503 1623 646 1833 1355 1913 1476 542 1740 181 528 595 1460 529 1712 1790 1286 1618 121 141 30 1408 1226 1503 1921 733 1112 1624 754 329 982 1779 716 553 57 175 1769 590 1179 1788 216 348 544 357 766 969 465 11 1817 952 998 1918 1526 1215 409 1249 583 674 1858 1230 847 1472 1806 1263 1155 1067 1548 1954 1812 570 1029 1827 930 626 1379 435 1080 131 748 489 1795 1114 1669 414 1257 1917 43 1273 498 655 1141 1109 1570 1125 443 448 997 82 102 1390 207 1059 1702 920 1010 585 1749 488 412 1807 1637 994 1876…
Output: 936696

Example 3:

Input: 1921 156277526 414847622 895199830 -635457 946350867 167139258 506868711 479531402 799737974 648921302 766095350 441369527 197293000 989877158 804322301 398041294 311705098 820754325 763495679 764017002 308106136 848252785 618881977 203269274 797944293 31795323 640431481 157064323 936385540 861983756 933489458 548651970 224222997 565080165 330390670 450682879 651307908 154261774 622844171 425960192 964074078 827639937 7483559 772091075 980495492 428160706 306807678 431071438 776459298 903055198 505338078 31047508 488483281 893709409 213888742 430231089 93006321 306838756 291793876 763109028 732636767 196127957 90462312 959114558 321919338 988485162 77338787 539880566 649990676 576985198 920189276 584548361 223245882 771599446 208257949 724459852 828835119 738807783 173267496 718013533 7504…
Output: 935504

Constraints:

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

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