CT46091

Herald and the Ancient registers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The assayer Herald has been asked to compute the guild dues owed. On the desk lies a long table of registers 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 <= 3120; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 2164 1676 1826 904 1958 2103 1016 386 1302 788 1875 768 442 791 868 156 2142 1113 2062 1061 736 109 245 1118 590 313 256 1305 1316 2101 2136 1121 1430 1690 1943 820 1689 1157 1523 673 1502 25 1071 1018 1702 1472 628 2012 1436 1182 1895 745 845 284 2004 854 995 1160 554 28 1501 1663 1847 1797 1985 1679 49 880 1216 157 259 2044 1718 169 421 72 1391 27 399 2148 304 1397 950 2080 1640 209 1410 502 1484 1349 2159 941 107 1708 393 695 1443 191 1564 469 1801 1 1394 3 1968 683 1152 1272 2000 564 1735 1992 1102 1694 1000 1086 1277 1253 197 1470 352 2156 84 1475 1750 412 2115 1874 265 1013 1381 54 1710 1235 1756 888 630 1681 1439 1727 1716 1749 1830 298 558 247 1382 471 1544 2113 2097 591 901 994 100 445 753 765 1238 641 61 1367 574 361 464 88 300 810 1342 2095 1266 1808 365 172 1153 424 1314 977 12…
Output: 1170879

Example 2:

Input: 2444 524652 379691 -252257 -158784 -908429 13247 690857 -360091 -578372 -80334 162593 -554520 -340916 -732649 -941848 -290096 -124401 -442280 840373 -483082 455647 -593869 350470 383960 -695922 483042 -826504 -906881 -560260 -768075 727335 -223184 690233 917638 -816336 -199434 -560232 517032 -796501 105520 -967820 545796 25413 624812 -929464 364215 -261928 -654963 133249 -156221 718143 -827024 -213197 215293 919325 -730887 -320298 149079 795922 -798811 662436 -126065 -292437 200430 550612 -482067 902674 -871558 -51517 -971850 812994 -164830 790351 -938572 -716049 -458389 786361 -704091 -939423 978431 -988765 430025 853881 -464574 623066 796751 971777 220738 912103 -937277 552945 192197 -545680 634193 -995184 103958 -807038 -363441 -790747 238119 669060 -484839 274879 -251167 -783697 208683…
Output: 1499555

Example 3:

Input: 1042 909243 -867152 42166 175643 -390942 270479 -444625 -999872 -839621 -969727 -353507 -822101 356201 -620942 93050 226584 -108777 -118269 -216566 -282213 -399831 -112866 472418 108369 -270930 935163 26193 154279 42921 332827 -382433 -881050 613503 -129630 23701 -145232 520945 200023 -656442 461484 638259 -340945 -746113 -21656 7197 597487 282166 -959347 -87793 -85057 -683342 -662890 -100398 -862464 -411272 889735 -648107 -720443 -977269 -453924 488258 921276 -615358 -611485 -453210 781079 74432 -272347 624038 -444942 118708 -111945 411330 -365300 2458 412847 127454 569287 -903976 4402 713358 821713 -752738 900620 -60438 -946366 -9258 -411698 253596 573054 -947755 -176620 -406503 398911 91990 48667 -991366 -624304 -103414 115780 130524 820726 801311 -709853 -212174 -420002 514367 7696 472…
Output: 266188

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Herald and the Ancient registers - MEDIUM Coding Problem | CodeTikki