CT46250

The Disorder Count of Blackglass

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the obsidian flows of Blackglass with crates of weights, and Owen the surveyor must account for every last one. 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 <= 3880; 0 <= a[i],x <= 1000000.

Example 1:

Input: 3057 1559 1377 328 1069 317 1766 1894 1229 1061 1713 1389 2621 2767 113 1714 2130 2407 669 2565 208 1056 2412 1208 450 2046 2545 2652 1936 2625 1363 2563 858 1859 1720 1811 532 553 1254 1173 761 22 984 2776 518 1120 1068 857 1219 1565 1637 2615 2950 2561 2380 2660 419 704 1380 1694 2718 399 997 881 299 1722 1577 1084 1668 1861 145 19 521 1886 823 501 2289 158 1163 2126 2360 1587 2809 1098 682 1993 1285 384 915 2333 3018 1281 1114 3030 69 1675 1556 1329 1586 487 2810 833 1224 296 1743 1312 512 2552 2305 2623 1545 235 1819 1344 1065 510 323 455 556 99 1276 1457 2041 1198 2518 27 1409 2736 2278 2488 1044 1828 1876 468 1868 2337 1060 185 1430 1283 2404 1716 2870 3016 699 250 1058 2350 1971 1723 1817 2423 44 1338 152 1989 2903 2704 2881 731 2383 679 119 3034 1133 2327 1659 1434 1834 768 416 158…
Output: 2346044

Example 2:

Input: 1793 946520 205876 27770 65045 885792 164511 457926 760270 369082 820619 389843 636999 605564 525223 938693 173765 164659 290270 102976 664326 593694 197437 490835 872600 253254 171277 903768 668425 33716 647789 485911 376429 219856 87496 186553 680234 679488 447276 452315 862657 318765 693435 838085 579277 820848 596785 259721 917757 150525 85409 981057 790495 988582 353486 25065 30640 660468 981070 753276 718783 305674 519864 587108 342495 823791 246350 844948 501600 175975 971291 366580 392871 568879 582708 154045 476785 985561 900173 847531 761942 612532 853111 785769 298113 393694 667512 422693 325309 961748 320300 129257 866885 428632 173082 63323 764730 736979 248891 268604 739625 764201 99977 440910 21153 187150 454261 642198 991327 81787 811916 87504 984054 387207 523365 631041 68…
Output: 798742

Example 3:

Input: 2851 107945 377332 361119 540070 188914 351134 482919 418648 347405 395579 879902 151521 274885 983295 465789 731310 632632 320462 23201 225599 567538 35487 27380 610560 119161 59179 979194 353126 852417 133398 194316 213779 703977 432095 972381 814992 289193 16375 29329 103491 932771 165234 465612 451011 232127 920063 789444 876707 894725 28737 304888 432167 138611 897507 917686 900235 365661 788695 132776 308715 242315 533527 693180 420890 723675 487602 135980 812368 95523 29744 28828 627767 755947 932263 323861 449873 569796 884392 313200 879526 738571 149795 630871 271146 893441 202786 265770 446694 754662 905075 54937 985469 364327 208381 427094 300442 702376 315548 336401 948167 545274 69531 327888 1808 349810 3614 927551 204929 870704 520832 923442 387308 998552 877559 592635 397930…
Output: 2002045

Constraints:

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

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