CT51015

The Disorder Count at Prismhaven

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Squire found an old ledger of ledgers in the print shop attic at the glass towers of Prismhaven. The margin notes pose a precise question. 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 <= 3909; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 1946 421403527 830777917 966848208 715884176 60015359 402115775 281596592 383935437 169730914 398019734 692632940 264621235 876459532 90409990 641069157 252601700 358297119 348105442 35745170 631009193 251392769 906398128 556303397 883186063 897089841 635145381 458281017 367108087 589695647 994679977 23609671 743165919 633779847 2200943 173668118 21159767 816938218 113061531 717968663 393409926 490279873 737092372 532159569 65790047 859349298 262109933 299387320 75350815 400217049 942217498 57542673 792437905 750335304 358505504 262519124 66004246 429265308 453075698 9226886 260074831 145327505 767627823 399001776 69678633 730795073 18195098 35220706 540045078 196402109 814546908 869473487 507935799 897482131 47041491 21547956 451480579 706203831 518549284 144899193 75801070 965539849 1836…
Output: 942252

Example 2:

Input: 3630 692 186 2638 1307 3419 552 2485 2389 785 1276 492 2329 3374 1112 2181 1065 59 1687 650 1128 962 3423 2002 2579 2165 2196 3330 2295 675 2235 3578 3236 2765 3249 3184 1698 2024 479 3621 3487 2224 1639 2807 1185 1841 2561 1223 2151 1606 1382 1028 2321 1395 228 3140 1690 2432 263 1842 2629 3405 1501 2831 2712 888 3168 410 2768 3090 3118 3152 170 1852 1155 3540 1241 3303 1713 1725 1641 1732 759 672 844 2344 120 2739 2549 2461 1249 2405 2398 616 3375 2668 3579 1317 313 2012 2238 2439 2451 3124 1797 1244 1297 2693 3467 342 3117 613 2987 2968 1877 789 1522 2102 2416 485 2141 19 3324 1486 3580 1200 1479 3472 3161 153 2754 959 805 1364 3530 1423 1703 1801 2574 1759 1091 1057 2131 68 2106 2495 2294 1771 755 3533 453 1416 3261 2476 2263 1142 2376 1782 726 1063 208 409 49 268 2101 3269 1514 1902 1…
Output: 3358990

Example 3:

Input: 1708 386622351 704808436 84702714 980976517 811577867 812501430 413235303 123165148 767114760 911208207 670916754 294983896 15484421 797746453 922217853 646922632 410900907 414388662 227295828 678738350 974175240 826086896 245293491 363111547 850961860 555756040 365907573 731299253 870115423 2327466 266463429 460462569 12591839 633859395 844664372 100981626 4016552 59532031 552267723 424096660 21996182 26033989 545854141 504060501 864377001 562577680 412151771 267547297 571552265 3505567 689353659 372813669 947929369 503106311 711287069 194142334 552535450 910461073 37379165 948824104 321797803 697397575 427765574 32647297 874885639 439408064 75001225 492115540 990419783 742336705 381733320 581911747 101479493 428414256 218116949 149424304 665021967 9266119 307839140 330746247 544832190 15…
Output: 711549

Constraints:

1 <= n <= 3909; 0 <= a[i],x <= 1000000000.

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