CT56019

Ysolde's Ledger of ledgers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Ysolde found an old ledger of ledgers in the studio attic at the alabaster quarry of Whitestone. 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 <= 3365; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 1583 87909686 783232873 954526299 724126034 256695015 709600386 305379710 361660434 699638244 199369392 618666794 289703983 89005635 426154282 360825145 285379127 984954354 108333497 228203891 920719063 585413356 999313197 258204229 406753559 541204508 263136526 620136783 820590009 627529208 451866679 304815069 439256770 250102443 928829233 276798625 679470686 423505013 324492704 19166601 352950303 423590230 180969688 68580649 516917446 825016297 715747047 418684298 696689179 703501989 485335484 331027993 207844213 32606021 986427573 315690603 587069414 134544526 81172134 231823924 149037401 487820094 128755971 749400144 224458925 39793603 889869948 35253432 816136884 105598725 698076326 217056567 515903131 657214819 871822559 348739091 628735662 689397931 200690573 539477576 499866949 971…
Output: 626616

Example 2:

Input: 3225 156878775 377370654 67830811 27224412 534962426 792141276 300203597 631350430 372036364 751290929 198422175 235636959 388897638 303235787 778203018 727209387 770349838 312672166 209635620 639333103 373075536 975986155 610901188 504025559 103268376 541073105 138055046 258977120 452113552 339238989 780392283 819062337 886675883 803253446 709638092 548425187 685525877 170915728 566845681 575645189 838773045 191955269 945115109 736321052 671535463 226723690 363686066 317795696 160626216 649930230 790075769 636912778 946804593 409746980 270408735 299817264 683613055 773248749 136301720 733387274 864020204 185924088 402292594 242443729 179973861 466716170 347749585 85065422 235639114 276204096 179861876 932557709 388555893 990132935 207416539 701409366 112926766 839700347 874006486 44411698…
Output: 2594602

Example 3:

Input: 1678 315942325 879363411 680339978 275361072 496542306 114855762 718124209 630223855 370234900 283576054 376231435 730971273 434210275 831657482 265151862 201029290 28009211 48815610 79886380 754690913 112980383 875963157 761399434 451655808 107510156 872351285 515744306 790945885 466282046 373061234 593663478 207687600 814422507 607710455 545729595 965797355 892652922 304922195 436617613 289979533 956398500 508583399 386583576 841098804 269679149 716055971 679650691 950865217 36239406 245962602 91619906 417415678 419441262 76080531 44123728 565753634 980160501 194252987 472891443 66003908 304904915 85317944 24807973 623337515 331115160 766117265 132644672 183938065 410342933 133218247 249446689 806923894 376177947 325525920 968377510 699060043 573866648 704926560 886679677 110369811 45904…
Output: 705497

Constraints:

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

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