CT45988

Finn's Copper Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the smokehouses of Brineport with crates of registers, and Finn the valuer 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 <= 3056; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 1935 619 819 134 125 1329 1843 741 1420 684 485 363 214 854 1725 836 635 1863 989 1095 472 1897 1644 842 1906 167 722 1729 920 1830 1850 348 1083 1651 952 74 880 1628 333 303 1522 1732 750 905 1052 585 490 1497 1099 778 1307 885 1222 1928 1421 1775 135 1190 515 379 1899 782 178 1408 1805 234 995 1436 1793 597 1111 1231 1859 251 1499 86 70 104 1442 1077 290 226 1025 795 126 1818 670 934 1078 514 349 1321 814 993 1549 445 1616 918 36 945 1684 605 696 15 1638 1610 399 633 1322 355 1158 1026 1933 1553 967 1724 1338 903 495 1779 771 1388 765 428 1490 1571 830 532 112 1148 603 600 1047 181 1269 1797 699 136 845 1814 417 1150 953 271 1905 801 1144 904 867 1309 1502 1273 34 416 1445 1884 1653 83 1718 1544 571 1546 869 746 1506 1488 124 1581 511 591 291 171 1720 757 1318 120 401 740 1772 1458 97 10…
Output: 941724

Example 2:

Input: 925 587480770 675308272 407759348 871241244 240203986 385635486 809874478 959746401 106645167 612216701 984898311 534249121 358214883 354988180 982558608 515344681 870922249 912639189 359552386 293641361 342946523 639252414 947532740 140470635 293892955 497590575 916091173 958996848 476907015 899485461 865707651 442367357 867850534 757983670 836618644 107707671 84763002 537908268 68951689 783530370 606293969 647574964 809180631 962979575 987719632 721677917 606617758 624353439 733955225 947188105 694180433 641001403 890262620 153606445 187257997 492953716 709129050 263001481 726192692 994138823 863606447 194856279 15758890 72844308 777590633 439562493 168988556 208478495 989182512 560616108 162303111 796208908 637245175 321449882 501190555 62304476 51254729 446338196 177451674 607653960 52…
Output: 216180

Example 3:

Input: 1193 746993216 640472598 287120788 230535682 186910083 470513524 240120100 73351026 745451221 293162590 287211827 838017781 182330472 109174059 823921890 222733511 822400295 524543755 208106748 420439710 124257340 538146442 393979604 235782277 611086486 520895816 257470162 624225056 391709034 749188509 828934753 925012732 188830385 465528501 719136760 802436867 806227627 490061016 780795524 832047173 410115158 204598703 342418650 412911892 713399822 246790918 886541593 211728009 64115651 378115354 270608652 904926554 125506849 479760589 549153697 690101531 90722664 439481594 545192642 112051492 217046362 315918489 231989227 353354051 34049070 465649384 123474898 592858267 359354834 403340571 878000384 608835415 723556744 710449084 272408566 962615827 86527712 559002360 470863580 614579463 …
Output: 369648

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.