CT51603

The Painted weights of Admiral

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The store warden Admiral has been asked to certify the cargo before shipping. On the desk lies a long table of weights readings. 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 <= 2671; 0 <= a[i],x <= 1000000.

Example 1:

Input: 931 893 78 551 557 580 255 492 800 650 334 627 493 118 48 304 802 422 474 502 212 65 782 100 375 892 305 430 770 528 841 417 165 476 206 106 922 716 885 84 136 481 764 327 291 908 511 328 762 276 552 92 342 56 120 448 874 843 829 863 700 601 639 824 726 929 536 323 728 640 808 119 835 219 850 409 452 463 761 169 756 416 787 549 692 239 757 743 418 231 458 382 814 345 322 878 250 596 376 553 268 788 866 665 484 606 865 412 870 725 718 517 486 634 611 338 351 399 838 839 673 200 532 379 842 427 133 857 30 773 619 758 347 203 145 636 179 595 35 653 420 583 832 372 69 163 296 464 590 426 701 450 621 139 147 37 898 397 51 495 696 224 711 771 626 259 775 175 134 162 355 579 720 816 63 12 487 916 510 0 103 167 880 713 318 362 637 772 576 234 310 796 702 126 23 406 654 53 656 741 519 859 208 652 2…
Output: 218463

Example 2:

Input: 562 257632 345796 143946 136923 793233 168920 473743 624784 977451 473945 721160 211131 584904 9208 63572 621827 940699 289037 553968 235359 315458 636755 337703 524768 165680 54556 628053 22888 889973 117190 503503 692638 96656 448992 131087 720384 593593 504204 870308 439540 260312 745284 760017 94169 522609 434374 194248 132823 509787 228872 486286 152519 173602 289371 517205 875867 162168 815612 513025 64823 512933 290861 297140 239513 430532 849197 351987 775535 178427 245155 99741 443066 528367 12215 719 296351 734154 574248 870674 617362 721002 57192 511205 255293 587070 936048 85230 732507 78699 715513 635675 834841 491230 578820 270548 874195 221671 935175 716581 713385 600624 839967 646977 490252 302453 251942 846104 750948 795901 335 282280 322355 999428 630430 112778 104920 528…
Output: 75659

Example 3:

Input: 2183 1487 460 48 2000 1345 1969 220 1490 188 1921 386 1822 1546 737 669 1343 1992 1696 849 801 202 342 1737 1932 95 367 978 626 145 1085 172 1177 644 1558 758 560 29 1784 1730 1931 488 1965 398 230 1943 1644 1126 2031 667 1665 352 2069 897 2030 838 768 1677 535 1736 185 1751 1278 902 1204 2135 1923 1063 514 705 1674 1562 806 1819 1206 1575 567 1049 388 1339 913 354 2123 1988 965 41 363 28 2 1647 93 170 351 112 1963 1901 527 1818 1089 1313 678 1620 745 490 1186 597 2118 1255 537 1907 54 646 1885 1024 303 394 1964 554 62 966 1603 1239 1309 910 2122 241 208 1381 2174 1641 252 1035 552 1823 1720 52 1300 435 1545 2104 1996 1326 1016 549 1809 1472 30 177 217 1865 2082 2140 2066 587 1018 128 214 491 886 150 1557 2141 1689 955 1554 881 448 244 1614 1742 749 826 2008 2074 2150 2095 1882 1430 160 16…
Output: 1145589

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Painted weights of Admiral - MEDIUM Coding Problem | CodeTikki