CT62684

Wynne's Ledger of registers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

It is audit day at the quays of Driftwood. Wynne spreads the registers records across the table and picks up a sharp pencil. 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 <= 2111; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 1963 253 69 1941 196 6 1739 747 1366 1845 1233 15 746 1556 1350 955 1509 1775 1730 451 917 616 1809 151 1456 320 476 1385 1859 1268 1296 380 1028 1184 1937 74 1798 1118 757 233 882 1828 1023 1524 1160 864 1808 583 1212 495 10 642 1480 1304 191 1419 748 628 1544 24 1850 462 1294 208 1370 1069 152 311 1168 339 1621 1181 390 1383 745 1933 1826 1411 1015 1397 1494 499 784 127 1016 180 296 782 1358 434 292 90 1144 1277 81 1717 23 132 1444 379 1699 1031 417 640 1780 436 1562 974 1345 1886 1367 1523 1106 503 1860 1484 922 161 1773 1772 982 1343 1001 967 1191 883 1273 1942 353 868 1852 1741 16 1163 1115 514 1601 769 1454 1700 1749 550 114 1180 1272 1247 949 1936 687 56 1274 1438 270 1857 383 1051 464 1302 966 1634 907 397 1354 1060 43 1146 427 609 983 1352 820 1500 1594 1035 1596 1286 674 1003 664…
Output: 976397

Example 2:

Input: 1558 -494378 -716730 9324 72082 100699 220231 -399790 -403245 512090 22965 -860253 -457486 195666 283496 147300 -232688 269251 659585 561683 667349 -929679 -483443 657008 -708515 623044 -360392 -222906 647063 -604565 -517445 163024 813931 -11447 240138 -139135 311669 674793 283939 232759 -645689 -341664 -437147 456127 716430 -668127 -855589 -625089 -540173 -405446 251551 -403996 134789 966748 -630182 -95143 -208252 -382739 -94837 -547429 -141917 43087 757350 -409416 559596 -243515 293929 -28247 809445 190918 -278870 -299475 687362 527539 -344577 -182193 -233406 570606 29597 -69112 437882 -633922 -232804 834519 154947 -666878 380399 -453562 -144742 -517308 -436926 -624863 -369613 160038 -299461 -953426 824797 -287466 77762 65874 694235 783092 904534 -912433 -602433 370667 920864 519564 -307…
Output: 603321

Example 3:

Input: 1577 185241 -14393 -545650 82349 490787 754918 673097 665127 -335017 652414 -656011 51458 616807 778107 65906 464243 610254 197762 399876 -914188 -411323 191125 46346 -47215 705768 -74563 269354 46432 -636823 608856 -638729 -551350 -407950 412771 90475 -703913 -528246 715158 -993155 -340848 132070 290818 -292781 -994085 -947100 -475853 412743 719222 564059 617952 10088 407124 29243 -83062 -480163 486052 -980054 796983 89357 992427 -391359 -182055 74823 -182243 -427167 -293561 -977697 -713076 721957 -906356 -715787 376053 996106 495328 95124 -410538 657905 -238606 -658671 -899978 -187098 378027 -548062 220452 -394061 81978 895498 136115 -424054 -720334 591936 -413588 224036 197245 648875 -759610 -279646 -768992 68437 178684 -754913 164103 -984622 -976244 967561 703330 330584 -298715 256893 …
Output: 614678

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Wynne's Ledger of registers - MEDIUM Coding Problem | CodeTikki