CT37107

The Greystone Disorder Count

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Vera the valuer watches over the shale slopes of Greystone's stores of crates. 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 <= 3145; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 2732 210126734 532269410 466954356 653744890 402923418 638697864 356050840 76954307 835926404 50511701 454914672 672868077 643553199 22172535 286517530 114963899 177256602 333621218 30732905 586409103 806664318 918671577 962952031 719726252 154599462 618449982 275755759 619644474 353709630 688572562 460551716 419856070 769353404 586833542 191910930 689639187 258923901 826628089 396186299 644721562 632155243 58710836 371978516 186705079 233551571 762580976 107380337 734977708 208692247 858956008 171237792 787961101 953757194 442280487 789285262 407463181 464684060 126491610 867408769 66362139 729989922 684487660 455333421 925715760 267039441 287352774 108554969 139913630 630967933 805653426 904777816 30800264 552705639 757017458 468531147 166242184 360523152 96994540 97582302 862345339 2290…
Output: 1836332

Example 2:

Input: 153 322836035 406171560 426091165 571974802 14647534 708637790 152937310 447165244 490798482 986361024 171839448 130467692 311456743 859201789 581210904 168362237 595110685 658233036 217440762 65505580 924849392 498960678 4481449 317737656 174986473 937279597 930502608 374494925 779528646 474655039 925292691 972405247 774402357 223757066 20656699 466097613 246523648 59028021 915573622 473720672 130341119 254825104 405614121 187294383 790793224 640497483 37085810 96028350 648002046 682495274 905646476 390121076 81147315 34212180 232093553 853892642 357362357 933716286 811678581 170006314 765661294 356850369 538896768 574698611 493388695 237580778 103164317 539378465 877721120 889946558 219670675 491162885 554458273 364610174 294545455 974765513 81943797 824776863 672476468 895192699 8967308…
Output: 5193

Example 3:

Input: 49 882205957 941019564 897451851 527124480 714312474 307115910 969231007 721550971 572787100 135004010 884490256 581558532 392556863 518166949 375575190 209282508 850222262 683069907 804246493 847976341 806592676 712622576 650931280 370978258 496396960 469114777 859655460 702555346 432265200 201938340 200727526 451197265 453698557 663568210 580903871 402189418 906570560 956315022 290500072 35290258 655713523 490484567 5421587 215337778 600749956 742026148 677816646 511678730 152855706
Output: 723

Constraints:

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

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