CT38300

The Disorder Count of Applerun

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Hugo the quartermaster watches over the orchard lands of Applerun's stores of vials. 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 <= 3360; 0 <= a[i],x <= 1000000.

Example 1:

Input: 2954 349348 127405 734602 751344 871700 750100 794841 253250 718327 687728 824645 169187 908418 861441 788565 376718 196134 558606 781223 191985 361636 965285 872464 332538 110302 157066 100214 994880 557665 872993 423429 851777 582456 171879 294363 749399 126699 698713 103797 910472 913394 377389 269863 590539 852118 790973 179396 95462 717956 380812 176814 192363 167154 32257 71183 652215 361028 662171 466011 869204 708339 747167 942342 621230 995944 19994 353594 941224 336372 266453 970427 969783 392698 698967 920899 74363 590890 840350 944303 653264 262076 932636 450019 337707 510213 167358 390292 19218 67231 253236 151593 869195 361687 397923 796144 939288 88892 486987 188596 325802 560104 25985 724273 319694 798923 713871 771785 245167 958228 868099 908294 205219 755226 954167 7618 8…
Output: 2206766

Example 2:

Input: 1476 884314 332036 19706 341741 452422 102891 704829 370672 691688 995258 600788 20498 281091 613823 870263 226924 796728 890762 955438 927829 914550 272031 642441 864174 744042 325690 295898 355377 576975 98504 449008 821942 462790 805835 88725 118099 800016 269609 971498 286707 949229 703789 708147 528275 289000 549235 789778 982303 212492 204 316080 606600 14002 374720 872166 275509 366106 29471 57631 860940 617531 554006 507237 12789 676086 259250 985553 861681 768852 513243 518517 624301 319518 349132 697365 847302 50050 379546 253896 247175 131977 744224 498807 270512 982709 713309 478300 783449 688626 405092 521038 694027 810997 234559 547880 665174 344361 182542 520687 845808 925576 928336 681758 477388 159949 990332 856553 184878 792803 193437 130193 322680 440360 767796 419150 14…
Output: 551696

Example 3:

Input: 1266 15689 523929 128028 8140 333282 10696 174809 682298 373409 710984 771521 179926 721829 908138 750973 711496 443108 485685 540294 367416 639475 641024 510161 829815 600702 284197 327912 583407 664096 812705 536003 656691 647939 212917 786877 165417 711890 726079 168166 533887 793516 188163 632070 175623 567880 256948 35662 749001 442132 357989 176058 400231 691992 890039 863126 976071 451173 23658 673824 524469 671652 166589 257415 222663 101862 730575 340503 342780 44282 638200 364862 448009 633969 753205 363 785961 641766 152337 911676 52890 299912 865163 609479 660837 823972 406588 438906 392838 37014 632872 324068 818543 455188 939503 818938 356455 616430 704048 299792 467564 727706 181314 684935 591319 346976 643144 199230 868278 946649 398658 216775 25775 679313 993868 7443 39825…
Output: 389165

Constraints:

1 <= n <= 3360; 0 <= a[i],x <= 1000000.

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