CT51730

The Disorder Count Beneath Screech Point

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Sahil the assayer watches over the gull cliffs of Screech Point'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 <= 3019; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 1827 951775891 176661652 815684710 782651889 305450149 226890599 362406015 561755671 454915059 214867506 556105620 30444510 800387168 78905959 413545339 723001331 150302448 912351478 401594865 199536510 353109647 353772279 232792492 566106589 222124400 501867020 124631705 418198729 993670725 137687755 632546971 628122615 298285781 842988153 620790088 950865247 367996343 281692733 347502329 546811821 759421310 64386983 714430177 300801494 409616035 184486905 264936096 554806584 541721063 190675486 929973839 581058903 107076799 655325282 849017016 306069558 889169637 876031984 929246846 672025431 128792331 219125149 268289160 718136708 681016455 848125103 238778247 891572029 167454852 647333290 679134937 968134274 477077062 214433933 703182957 69366692 920991158 249694385 659183528 495796764…
Output: 845837

Example 2:

Input: 55 92207607 390759401 819280072 176094613 243348102 147239330 249670246 122946185 250793005 681634023 224652838 294896942 813457760 508222085 444133350 295501532 579720622 304528017 880079713 440115679 336111260 155674734 723484190 444280165 690879040 22700391 774936367 654265537 119412284 658752673 148571094 147143668 484408143 508122132 711080718 337028897 323000767 776650942 414458194 267823419 47622782 575275488 465233 759887457 470265308 644696001 477817747 473149216 951407183 620465587 372356352 619349337 353757952 315105537 797604094
Output: 621

Example 3:

Input: 1758 431226966 965586706 366305431 724455728 895660361 181522919 376470485 23468118 434530722 263990658 355611165 206370413 719641956 725505237 276003866 135706253 315157653 613139659 435155986 737416626 445920655 767184844 139225935 590969871 134040062 804220281 466775644 447956281 245991636 49631296 970210266 366683125 56010947 270419182 444641925 266374623 736195775 514485425 719974135 709273011 837259099 586775615 32237180 293878718 883001448 48877192 709049570 694336489 588013208 242380735 418607771 117653365 644644289 236124169 397102302 546026629 616217503 926268707 506932938 229277410 13494598 752829292 65790186 940152515 826969078 306780757 853957272 770857504 153864900 563719901 18320270 477408651 807548681 795128543 621426557 993342702 792964790 436685919 126637346 185739812 483…
Output: 769750

Constraints:

1 <= n <= 3019; 0 <= a[i],x <= 1000000000.

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