CT59299

Wade's weights Disorder Count

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Wade found an old ledger of weights in the apothecary attic at the snowberry thicket of Winterholt. 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 <= 3200; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 1917 -714486 -476187 -979228 -872880 -593980 -33445 -321028 -277831 399643 345748 504425 219166 -429503 -583520 40189 425004 -468730 -179718 -965305 761565 -623903 575927 -861545 484013 14844 906683 -296943 -951313 -722581 -445533 102620 -543898 518080 -955523 846298 -142969 239644 -156198 -847774 -913508 -81640 814047 781991 -279521 -296735 -230583 890288 -33889 720166 -668572 799578 -133901 773962 78435 37085 686013 642159 52341 -294428 -812665 -174553 229838 -239934 625549 -298682 -382237 -513889 -545164 136265 -396135 -12644 -809834 -232101 -597524 -23079 -608954 190093 -548888 -399179 -226854 211407 186907 -245496 681685 -308740 -966038 -379671 -664448 551632 276027 771469 -696626 274586 -684095 75221 433790 -667382 -282119 -838028 -269282 -246440 352458 -674279 673736 -304263 324966 …
Output: 916013

Example 2:

Input: 49 156954 753970 608492 -137524 380598 -287685 -894247 120589 807885 196691 -945680 380861 29723 488609 772827 -785632 -93145 -399462 -835262 811848 141380 529039 664404 635422 -222983 -959798 -535239 -175241 109060 141245 -612146 -634079 346601 -897897 -364289 -757669 -184453 166583 -532571 -180136 665445 -558480 -928896 -379748 852024 -935437 -882215 -15223 336958
Output: 695

Example 3:

Input: 2155 363000 163400 -699485 -845745 -409686 -260477 -166785 -11918 873431 618640 979394 -405996 -677002 -340816 601062 557932 -250238 -358783 710723 877088 194600 -116455 -898736 815167 -91567 788109 -927369 -790932 -658478 961819 797070 628964 442199 -398520 -833749 574553 580898 -613603 951611 -74022 -601298 211396 251549 -670821 611018 -112368 285746 -943319 -490352 963162 -794374 909751 554797 525491 -312261 -740427 65835 -883439 -542167 38297 574943 833541 -234188 -18005 -922101 -961523 570285 -367329 557959 -217415 -605936 -547093 -616522 612763 266364 -482858 -308377 -542526 792932 270324 927710 -755576 224081 568053 550020 -926052 416745 925693 -297616 128086 -191058 -590955 -623414 -638722 -763739 -613484 -87639 -705556 259958 907971 -616236 -421183 30316 31574 -136458 482842 11563…
Output: 1144126

Constraints:

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

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