CT55149

The Disorder Count of Nacre Bay

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Deep in the pearl fisheries of Nacre Bay, Theo studies rows of registers entries. One clean number will settle the guild's oldest argument. 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 <= 2582; 0 <= a[i],x <= 1000000.

Example 1:

Input: 2060 1652 826 719 228 1604 1716 1251 362 102 1561 1983 1256 1761 43 940 370 1853 1831 1436 1485 2011 1153 949 199 68 1346 696 644 1986 671 119 484 1672 162 1500 684 1381 1516 774 707 1160 1621 839 391 1273 916 2006 1466 1299 2051 248 581 784 1465 475 159 292 1353 1206 1790 433 646 970 231 1202 1129 600 1326 437 1290 481 407 1434 1969 682 1035 840 1259 1117 639 1427 1718 1956 1785 1180 715 731 794 483 1418 1734 372 513 1562 53 2002 601 1321 1195 1370 1906 1571 1928 979 1313 2046 191 365 295 818 1759 525 165 1477 1980 1677 2018 499 1828 1987 1310 210 556 1984 592 1071 1134 257 569 1269 1880 708 758 1042 1367 919 143 1647 1598 1231 1814 1457 1360 1355 958 2019 797 1833 364 233 1244 1285 610 197 875 1309 543 1965 945 1098 1338 522 859 414 1237 1433 1429 1492 500 1157 969 658 213 215 1715 770 1…
Output: 1056779

Example 2:

Input: 1800 505976 667967 393899 688664 283336 110743 191093 504103 202360 85379 363962 73793 266917 986263 56838 125797 649146 538779 183157 85766 939750 193030 532321 160515 673930 118116 982916 874481 336862 909942 962253 556862 878587 592343 824284 537365 177292 505547 729195 421674 544083 449973 349713 356589 551023 916138 493041 928676 341049 323323 157882 905322 717976 622051 65851 842361 116627 328017 936822 110967 428970 598867 299697 15251 150545 787684 821388 975619 704888 693485 344840 717536 163138 259246 599832 866582 991985 173770 607053 167275 437021 488729 84654 604290 512145 881957 510509 745563 167294 496303 114214 384132 319157 435883 942210 557834 540811 71597 108178 819486 138255 347080 35452 372056 989107 555217 356182 378801 241853 198840 449880 764181 557113 80640 317681 …
Output: 795073

Example 3:

Input: 122 295465 345268 319386 949496 552587 654410 590222 584865 299719 297997 338845 256930 721984 903076 137877 417657 156492 70543 568125 196523 554360 641277 697359 817699 723124 67608 66653 725143 738399 967892 319054 215484 644251 956535 882029 339674 400053 164099 111592 910770 200810 209130 381882 988794 789002 585981 522155 590976 95258 622363 95562 138210 86444 678869 640870 895089 923522 524762 960253 136497 20099 523623 306838 191627 31168 169855 647287 492016 448523 260713 6928 738245 885567 576410 921720 522120 913826 394275 203179 566145 917630 290918 731181 813767 644930 814058 213650 432059 786104 841505 375669 313944 62706 642020 118937 466193 549871 617706 294891 408281 513147 274771 567445 530108 539195 543025 24473 346403 189306 19025 960772 112096 146148 855112 299082 5264…
Output: 3753

Constraints:

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

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