CT65064

The Disorder Count Beneath Stormrest

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Before the gates of the cliffside roost of Stormrest close for winter, Sable must finish the registers ledger - one figure at a time. 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 <= 3574; 0 <= a[i],x <= 1000000.

Example 1:

Input: 1458 156 610 1034 1324 98 158 765 1454 1392 962 264 142 207 452 474 1354 1002 1118 330 35 1382 1387 824 1410 1396 265 224 849 1023 341 990 10 40 863 1287 1084 561 675 1345 337 23 83 382 560 713 115 441 347 259 1207 803 522 1085 556 538 430 229 55 905 433 909 240 1278 420 61 942 698 1202 1203 1279 605 523 978 476 336 1337 619 1424 859 692 399 380 651 838 941 1291 351 355 267 583 302 754 1175 865 144 293 1033 1426 733 805 518 947 679 526 1177 1219 92 280 548 190 1133 3 545 239 364 145 1294 375 836 13 1036 1369 705 1077 925 1043 494 876 1052 564 1297 892 934 97 841 984 516 1284 1320 577 862 233 1236 782 1339 210 87 835 542 17 1455 1165 251 681 271 1126 496 1197 997 568 854 1157 844 1277 551 588 776 596 1235 365 626 606 998 1288 176 352 989 1349 398 1112 30 155 1067 149 1321 1049 553 171 749 4…
Output: 516554

Example 2:

Input: 2241 259147 559009 312798 318073 47722 811179 992181 342250 623422 481974 638527 13812 868908 87775 984447 831201 506659 422122 837441 331881 774114 500452 362074 575285 175230 940425 731544 88244 447844 542557 23268 199350 861869 375444 48526 987488 463854 494866 232617 555249 77150 108146 737416 589370 371122 440468 264619 471613 270210 93072 421707 157412 301429 173274 750286 854448 62828 622995 183572 927360 789119 674776 539419 353475 811171 76501 321507 225447 601315 921820 891002 206091 107733 993567 851941 929009 501155 666610 657254 825170 504790 119887 576551 66879 720764 896717 517511 674542 127251 841111 777203 311170 293610 434080 385914 924592 381506 393072 863495 567391 34546 177363 107217 669328 138257 435707 176470 963087 510234 988338 439859 667727 492573 865035 223527 94…
Output: 1226390

Example 3:

Input: 2534 889 1022 728 258 2328 1219 2217 2511 1903 1686 1141 1009 1690 857 2434 1476 1853 29 251 304 1517 1026 910 578 2497 179 2447 944 2460 1335 2405 2027 1163 2263 999 760 877 254 45 1000 2316 158 332 1629 509 942 2519 372 951 535 1637 1952 1763 111 270 1106 852 703 492 707 343 1998 403 523 2464 2314 2224 195 161 47 487 1597 1519 1729 1188 821 540 807 975 2067 1491 717 160 1098 1710 2183 2275 2202 383 2362 928 1868 1162 722 76 2104 425 114 1948 1261 508 2505 1931 2524 1598 828 1286 1865 1427 1668 926 766 155 433 1569 2112 968 2039 2071 1969 2499 1644 2354 389 414 705 151 1049 1110 182 1769 2266 737 730 590 1800 1927 2407 916 1777 2171 399 1726 55 560 1788 1348 1709 1824 1472 764 1958 1855 2237 1839 397 1785 1563 2501 1930 1086 1873 2438 1053 802 2175 122 2246 1973 1267 1329 2050 1514 1377 1…
Output: 1629704

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Disorder Count Beneath Stormrest - MEDIUM Coding Problem | CodeTikki