CT61101

The Mirrormere Disorder Count

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Every season at the lakeside town of Mirrormere, someone must prove the quality of the harvest. This year the task falls to Isha, armed only with the ledgers register. 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 <= 3486; 0 <= a[i],x <= 1000000.

Example 1:

Input: 3042 643271 768168 587176 120594 540146 173492 260883 909744 417520 322604 427974 988906 934768 53638 495993 856844 128406 293235 923772 320399 457856 469327 325331 239179 306546 167566 497954 770796 875691 701760 765801 666798 995853 774681 833439 636674 491177 152885 725799 634740 628493 765075 294757 906898 825575 266802 716644 621505 92202 154235 750796 999993 419781 546320 174840 949813 644406 935493 36116 557067 567069 263063 616746 718986 944286 319042 753117 824528 980953 624870 709902 171200 532633 295493 808577 641832 837696 152071 158076 447731 784566 926984 976924 518475 54558 513829 888508 429091 225159 577031 814664 665404 620136 199690 242736 106847 890569 931102 942883 638205 673575 768087 785463 437750 139001 208037 524362 709231 409789 421671 485283 323426 545397 148952 7…
Output: 2322605

Example 2:

Input: 3150 866116 471392 833268 495699 908686 598944 565212 239116 210619 799950 768333 406660 731298 386351 790681 556975 348421 247690 541431 833672 979725 113818 912579 713677 780780 471518 838136 64168 753749 580873 472750 142795 658371 917745 50052 595277 313386 332115 12368 675183 559806 391914 269342 321176 992366 480204 825394 855555 817608 874922 194320 103925 390234 997484 323637 365831 569391 816952 770858 252389 822518 33939 550931 919502 548446 225141 968373 852658 973786 750467 474039 8974 962877 369966 435893 354506 48363 20403 985639 893531 938694 833158 219016 792323 987550 636519 213423 548268 607305 219313 557216 422339 691434 337180 557878 745922 692541 955562 122125 784755 964610 584917 370897 244166 614809 105648 69204 916960 961453 914390 29582 554105 482484 197450 369396 …
Output: 2497929

Example 3:

Input: 3108 792857 740430 676316 892628 448283 40445 772473 282431 478995 455732 501112 789671 823235 764749 862483 774826 556134 816957 522492 243757 437157 264396 111385 4392 853643 232101 637480 50186 634 974359 980570 819819 486892 701084 706739 515871 647563 556218 692951 943464 986327 181753 323969 866491 155431 420700 751916 258866 551325 168648 94745 391177 599992 953749 311430 908743 348654 452185 588408 23105 5453 275101 332089 388187 191126 477345 994291 374363 909210 933697 28226 18951 435244 797669 83958 662734 565243 239794 569472 765904 873054 917570 753673 254050 652770 19608 266506 773438 182458 605960 487575 132367 379665 636530 791366 166790 125813 807824 353229 561928 833871 121756 469340 668445 330674 527221 993827 600983 706163 829364 683900 222984 270021 469949 792072 65744…
Output: 2415354

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Mirrormere Disorder Count - MEDIUM Coding Problem | CodeTikki