CT42211

The Disorder Count of the Polished crates

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Vera the assayer watches over the shipyard of Keelwind's stores of crates. A careful computation stands between order and chaos. 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 <= 2941; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 1954 499216 148618 689871 898181 -975521 442087 -423221 476153 -512774 -363211 579245 39242 -792291 -443708 -205694 -308221 -82083 442752 -122831 -146142 784688 -927502 -263522 -767214 383485 -3281 -311989 -509965 -134731 -119953 718553 -645385 -120656 -350145 739541 886324 565705 330986 -513169 -536325 831093 441900 413071 -108289 610482 803308 13047 615834 145767 -780579 161714 -791010 998180 571331 -865915 -260862 -770483 329874 -309497 -97311 891341 -827821 -60408 443759 364313 478068 -269449 218269 -83690 -24583 -154929 710934 -370438 266868 -690248 187211 -472436 -578140 256948 -370925 -477830 -281218 36419 170729 -746494 579645 416155 370912 797566 369413 -499251 -17517 -442819 -423344 645233 708697 -636883 742379 333211 647666 362569 -51277 -62455 -294547 925906 992409 -783368 1586…
Output: 967234

Example 2:

Input: 1480 550114 620899 -707303 747835 728610 217562 43418 990907 509786 -441053 -860481 -490723 160828 -945262 752938 -927671 565810 77375 47676 155830 -214583 -434319 -296430 155164 820824 -752552 -267136 -212067 573448 100906 -339770 122543 -696643 237068 978580 134114 -784169 332705 -533790 15721 -403948 232512 -928420 -362226 -524360 -155748 310299 273313 488295 -117774 504141 -71027 731354 -793006 456836 -381125 -42249 -104239 659164 -138585 369045 116153 -649984 464102 -954408 374400 556814 -443693 40384 -419852 57377 -503730 856605 -7975 183514 -737220 -848132 818260 843768 577531 -633738 -759176 -212746 -916504 140315 733649 -612183 569616 832675 25137 834934 869763 391569 -578057 827838 702950 651202 260457 12074 243180 -837167 -908698 155022 -935766 420436 -296549 -587930 990999 -724…
Output: 549995

Example 3:

Input: 712 776596 -835537 -198506 599865 391301 -352616 334901 -963736 736882 484733 476483 -428918 -477631 775025 -168060 -437119 379648 -496332 -345534 -453882 -105859 319034 -14149 658311 10032 -147335 -442290 -381813 -181145 933820 -454724 -421065 699201 145846 311190 -7858 -411995 -60206 322429 95044 600654 858487 -111592 587043 388598 309663 34703 -69016 -257186 -192813 548014 314744 905771 -438416 625458 -792720 951936 89136 -691255 -360080 -52722 633654 811939 956699 617765 802523 -587279 -492311 -820145 782077 -309755 747226 125939 919646 -330743 385397 672457 -787790 -793932 304297 932185 913428 884409 504960 -725189 -224189 -704114 -709999 165714 317858 707074 691288 -551681 325922 -393361 900913 -55339 905266 168266 799658 -514056 133600 32362 323948 709294 887450 -837709 -851537 5012…
Output: 133527

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Disorder Count of the Polished crates - MEDIUM Coding Problem | CodeTikki