CT45080

The Disorder Count Beneath Redrock

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Tarun runs the depot at the canyon post of Redrock. Today the books show a list of registers, and the numbers must be worked out before sundown. 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 <= 3157; 0 <= a[i],x <= 1000000.

Example 1:

Input: 2592 988748 346696 85011 51721 541062 19948 321991 391875 610208 883676 757238 486819 389372 542185 353770 426861 266523 270751 997712 677704 339789 964595 119682 360255 873414 225002 13237 877580 947935 335719 163462 863438 239136 369092 92369 98933 778831 86002 301689 967210 435251 730735 518382 927637 277801 726189 877017 805693 256279 105993 563205 570251 836442 716528 674789 503313 981446 829953 261892 60997 891628 417432 97405 127848 32957 531631 624550 439514 249418 807841 349193 75371 317526 122674 269004 221926 714550 112460 912851 727861 401807 345208 327685 211271 656210 696733 325497 390227 140606 948338 555837 9374 291611 82828 535180 684502 641734 743333 939178 614573 961091 102146 102839 761884 370924 215715 136051 227260 422204 713211 884154 302141 600814 645908 313789 6989…
Output: 1643607

Example 2:

Input: 903 231637 844959 485849 1225 615752 490881 186746 188534 156589 221975 744188 506869 885714 532011 454867 509888 545992 586951 331037 166602 973356 156186 807734 620983 122349 110927 423244 179673 524100 526713 389781 297236 668773 893537 406561 652174 374540 448195 942836 553676 385950 984225 168352 536870 996251 344385 161416 196629 683338 398906 25458 434689 842579 603675 419260 140952 755444 53549 502562 660570 43080 317211 776183 339104 560785 415908 93635 441801 952073 328299 630519 370423 722009 992018 651207 216830 674556 140792 902421 132724 209396 799997 705713 741573 535312 655418 655468 550244 682643 239689 696693 28707 715889 172615 598520 440442 282163 525929 53629 276375 227091 639608 696980 648538 807010 678000 613703 276570 604 309258 244229 279994 908983 227354 236019 12…
Output: 204453

Example 3:

Input: 2088 69170 265373 102967 291981 802502 78681 284134 283350 696820 510378 992257 673970 512265 603343 380793 517538 382531 968091 459787 339614 848475 807477 696505 443072 3295 173160 716493 667942 401205 283950 679354 762355 153720 718423 317173 13494 304036 162544 820214 336812 162609 901880 671490 671910 318610 512559 370423 203671 26359 854704 867079 789655 881054 939568 552487 950567 885635 568462 195436 616837 518523 237077 499218 459122 658356 156431 441188 225405 821712 738381 529086 111034 128635 76215 616615 395454 909114 120853 774768 525494 610052 308662 98800 872055 433684 787721 282160 783289 455061 176154 317701 11657 481835 326077 341983 510536 812822 618347 731097 675719 29148 174765 375998 456001 202579 460180 238697 704316 923377 177896 484037 2275 269938 637381 121638 84…
Output: 1067624

Constraints:

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

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