CT51538

Ysolde's Disorder Count Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the marble forum of Argentium opens only for a perfect tally of vials. Ysolde means to find out. 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 <= 2213; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 734 191970302 606612797 624843738 434752039 791581149 230280901 101778979 289048004 723781315 767724463 429196597 144049543 373618939 310482333 877903845 384906628 960155934 758034223 508363088 637198925 765072949 835632052 834692186 145593476 672590863 291706663 741456446 324022658 314498248 619198948 456346103 281166553 892062599 769827430 878768988 807710358 293955087 449841488 123041644 792991189 165870306 621970638 241492500 120773835 438771981 433061481 292491450 484863909 809014713 738233255 691776274 720695156 403318365 636152439 378048922 721972901 574463305 573163680 341153646 433011968 490815113 105724690 97222948 369626528 134390770 569105117 164980292 894913902 121038110 809655728 277647160 470821454 543985232 976080007 279628022 663863730 482874164 950197076 110922383 1036775…
Output: 130123

Example 2:

Input: 2185 1721 747 230 999 331 417 2010 1323 1844 1674 1723 951 1331 249 1322 314 272 1184 811 374 1558 2135 1661 1908 1416 348 1130 439 1312 529 1474 319 168 718 2014 396 1305 1914 2039 1160 295 515 1693 1702 944 1910 1901 563 803 110 1816 186 691 1021 1229 1569 1710 69 871 1413 1694 1398 1909 608 1972 471 1528 650 1040 1977 865 232 479 852 1563 250 1363 268 2178 1776 1518 1101 465 953 279 501 2052 1645 2105 1471 1003 1597 306 388 1531 1532 1458 791 228 377 147 1248 2153 1406 1507 1686 949 300 672 1049 779 844 827 2166 6 1313 434 350 427 520 1028 2036 47 547 16 1594 95 1086 647 2006 1829 881 765 184 1135 1178 1239 1062 788 1380 1622 603 519 275 298 1927 1210 2030 1013 1967 446 1882 1665 596 2162 1846 1583 1544 362 2133 152 1140 1538 1121 541 1260 1540 692 196 28 1288 390 1036 945 768 1345 821 …
Output: 1190090

Example 3:

Input: 230 152435059 619887693 31673690 391762697 578337902 25758421 345702150 245574332 926539095 666024839 616072562 479857109 74408605 844864748 890083589 936410448 339300645 673312043 920460269 978701457 516725251 9096907 875457547 152628563 512394928 494394697 316570303 89187309 652501095 717718894 742467137 219895948 866732763 275254276 757559568 922108931 422755026 230627722 203762626 317976576 972120063 937506197 631280622 617741624 123385623 653982394 733223966 46242990 499686355 405934746 496911169 933290024 294123006 268067134 243386986 779875402 704810472 96088728 536377625 120717690 719373098 328795786 155426400 385308550 608925226 840936179 68201812 337897595 63428553 750206413 227543008 380722978 54797665 225343378 980917251 940114151 278774191 661818751 733966113 930178295 2884662…
Output: 13202

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Ysolde's Disorder Count Ledger - MEDIUM Coding Problem | CodeTikki