CT41032

Scribe's registers Disorder Count

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the windmill fields of Gusthaven. Scribe spreads the registers records across the table and picks up a sharp pencil. 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 <= 2542; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 838 -242813 340846 -390385 674615 -287504 716886 890154 -240788 133930 -833016 -738872 621368 -158436 337285 950677 584403 -824110 805722 -787217 36412 733849 671193 276582 -353914 -579532 785789 600505 332893 788856 -131784 847719 -528680 698914 94225 359193 -748344 657954 -386574 3783 -755376 -937663 792633 165285 -501386 -432041 477629 -606673 -794785 328295 -503218 -974400 -415640 -330208 -698276 -436399 691334 -981948 834568 250169 729738 -613355 97686 843747 -261380 987136 -818520 -991005 -592493 441934 310716 570158 604229 162159 -131598 465130 70283 -566304 899863 -970621 125862 -754621 641237 770463 -800542 -244213 810015 264151 368146 400699 -375634 798769 15100 454723 49237 -996611 722835 37780 -205413 934858 90398 -441764 -937275 -923315 -739231 942543 166434 -816694 -907649 65…
Output: 172356

Example 2:

Input: 1129 -991426 365029 -466063 367461 -669985 -978648 -34827 -709710 -889428 -119823 -319583 677775 442873 652626 597150 787976 935001 -525669 42941 651707 -936991 221812 -787076 620624 533557 -941211 -855275 -125405 840906 -121814 113636 28720 -662580 -479499 206742 -338986 922437 768883 -532063 644561 824349 880495 -729752 -974411 861336 706697 -323243 -978821 -885846 -423279 353242 -651903 531823 966899 -344614 427756 -352775 665430 634355 142991 -678357 -653910 -249303 -492475 -371431 668659 -480743 312300 983608 385443 -406029 384581 -588667 -806434 -240165 935620 -282957 886750 -566181 220646 -882746 969030 -10518 -593650 -964497 814486 -32950 -91052 973406 -881289 -470536 -118093 -221101 812877 -192029 -256062 692486 -716434 730736 663161 -759455 -106844 663521 -891062 680475 -110956 8…
Output: 308323

Example 3:

Input: 2102 816836 -216356 -543369 -431836 258794 -857843 275797 -556189 -984655 -469371 52076 -757118 861562 -622786 -200632 889415 -750910 286618 498354 548720 483621 -263165 672122 -279805 727202 -271382 -999580 302064 430411 936090 909877 137593 -827087 -264467 633790 187825 106000 -193625 -655172 831252 -958987 120755 64253 948115 52588 -189876 -777915 -568200 -130572 727504 64478 231944 -86759 -59103 524116 -841696 -113657 248747 425938 627159 692224 -739089 995224 309853 144119 643148 403877 -458106 340361 410687 -199138 -343648 -449564 273195 213126 340739 -698484 574090 -921871 -723754 -580815 -289644 -522015 -401299 -595519 -463109 778911 -358678 -886794 485996 162941 -443801 -517158 -156076 -663518 891627 289665 228611 322286 62997 -887029 811889 -151468 990430 -216818 -359520 449771 -…
Output: 1127314

Constraints:

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

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