CT60480

Kabir and the Disorder Count

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Caravans arrive at the copper works of Verdigris with crates of weights, and Kabir the reckoner 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 <= 3396; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 2722 -498627 581486 -6720 516665 -340544 -419470 -921455 -367264 274247 -865767 244311 -274015 279068 623496 347347 -696604 -457790 -121552 -387335 385864 -666173 249116 445365 167040 -400356 -409485 -289558 -979473 -582046 254020 40184 88823 438715 19261 -343168 6525 -967145 -798074 237169 -998864 -247273 -529617 323396 -427227 -181652 -69471 282815 -903867 -156644 -328562 816143 161824 718399 -975226 -44445 737444 -487284 645782 -878049 -539371 452264 -63363 -722356 136204 -988024 861361 -587873 -814270 459278 -467328 102781 -490833 444022 38739 105685 670175 911467 672389 503850 56456 -290723 -455354 807113 -886820 -298748 -557175 -663655 -6017 -250572 -110636 602121 891500 99348 941118 583362 -120749 705598 -911080 984827 -289040 -742706 -294239 -359383 557538 700756 759042 6841 -50112…
Output: 1852090

Example 2:

Input: 1846 601 1472 1748 87 1088 1210 521 818 285 556 1175 599 1302 290 17 1597 1522 73 639 711 466 1576 1647 1395 1154 449 773 1822 215 47 502 856 291 471 670 766 1262 1177 1513 983 573 717 65 263 1705 1635 954 1776 112 1343 443 1362 1269 509 1349 1750 422 1161 1688 1167 224 69 1336 456 855 1680 980 208 725 167 775 468 1387 495 594 646 1014 25 32 341 610 1294 690 523 565 1754 1084 630 948 452 1389 1012 752 1147 1100 132 680 873 607 1070 1538 1812 37 1496 1623 1503 1768 187 1149 1288 1004 700 188 104 967 1806 1163 384 1060 621 1642 508 1620 1308 1815 1355 849 529 884 890 701 286 142 1423 642 974 968 266 1665 410 316 368 1722 234 28 1821 1283 1469 866 684 1716 1789 1463 470 1618 0 109 737 64 1840 117 1171 1608 981 641 549 72 1442 1218 1285 1651 280 482 146 1312 1353 211 992 1610 1585 1555 1447 45…
Output: 843431

Example 3:

Input: 235 -33353 -924074 160581 -372028 788817 921150 907215 -945650 -427362 -916613 175054 540761 276994 264484 320415 -581348 -491911 -497422 575501 -676452 -484368 -237196 -804551 -48015 -472513 -430036 -477865 587159 640405 -901513 19165 940371 83746 -109855 -905806 -404042 932082 -86995 801086 -363258 302986 -542299 684394 401489 125692 750153 743050 254160 -695030 -773278 -677878 226062 -636634 867160 -76448 -453394 492819 807843 -109873 654509 -173894 730229 -180334 -288395 -675783 -211576 741982 -187172 944089 -665880 -117067 -408645 112946 -10103 -493208 -41339 397782 -353992 -963985 -524397 -842547 -768717 -456923 -759707 -168591 391957 723486 -860310 -79412 176167 -448429 -967433 475440 996132 956745 411681 -595852 -996589 -569370 -77295 -353540 -30955 -929173 456932 -376962 -473441 -…
Output: 13022

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Kabir and the Disorder Count - MEDIUM Coding Problem | CodeTikki