CT52189

The Disorder Count Beneath Rushing Falls

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the salmon ladder of Rushing Falls, Galen the ledger master keeps careful count of the crates. rank apprentices for the new term, every figure matters. 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 <= 3285; 0 <= a[i],x <= 1000000.

Example 1:

Input: 2150 519269 284562 231337 469258 164372 997732 645943 99990 959402 302764 926068 344713 833783 165068 857413 630877 998510 778667 88474 139866 879929 412071 308520 690964 588154 347879 455911 937592 817087 973350 179983 508152 872253 577472 663878 708348 502656 94976 556972 857694 973858 865967 72765 155357 334125 951231 865234 147824 803390 374736 974187 419400 979567 283154 733605 498787 847300 612793 418116 641503 562111 476789 715208 303641 217942 101458 607108 560046 385958 180868 332957 531183 449223 311391 902293 600577 402709 750283 440136 991259 514661 436310 739608 446223 285395 250761 971821 141532 921149 821865 869121 438518 949434 649128 926718 790047 891915 55281 172344 964041 428460 845820 233810 841319 733765 15116 434525 314050 980174 183039 137083 664105 566974 18253 2876…
Output: 1173393

Example 2:

Input: 2941 876193 587989 898439 78618 965412 634063 249929 936733 658706 781728 627255 979108 78436 830947 645599 123857 785662 687767 11938 157022 636648 40818 834954 746360 667512 575880 579782 963923 399077 268313 797351 566882 567168 526799 710380 409096 154671 892982 901063 418261 354825 485613 180235 486331 781714 327098 19602 240974 407163 253157 581438 800382 832363 508162 984977 546575 182105 673830 926927 50488 76532 219132 89580 524473 269120 861584 752152 574890 239835 543985 647073 788691 219284 338247 318744 162867 545507 431194 189545 741188 357494 655197 966193 38590 131509 543192 256508 151985 744707 870786 197672 444334 773674 551076 240226 709907 687106 563593 140023 544514 261943 82650 384082 258589 583646 717580 802438 179528 766189 930305 754920 54430 636430 826318 187609 4…
Output: 2162398

Example 3:

Input: 3061 585133 515685 44673 199033 448884 789172 816508 86081 768869 811285 482415 273222 121538 284239 145190 169494 978124 947511 336049 355807 525712 484565 265503 693243 234658 507027 70336 597913 973660 511821 168290 181080 485097 229191 880105 483665 138160 553236 427793 835222 80351 437574 89632 329181 975566 477632 208234 284203 39270 385696 231337 485456 497721 686742 675187 560229 549264 554342 495566 128234 629579 142198 935549 273329 50345 869451 575304 942827 946695 967803 10550 954583 114719 297818 419673 919125 811141 589514 290209 464129 616682 799180 583898 114028 771987 673863 719393 100500 888483 20086 909493 359754 675051 701712 954516 830148 89978 700830 575200 823130 224344 443100 58675 424395 21629 642351 571758 701118 62765 53824 101356 848091 388694 258051 172731 8098…
Output: 2344689

Constraints:

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

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