CT54291

Wren and the Disorder Count

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Wren found an old ledger of crates in the workshop attic at the mangrove channels of Rootwater. The margin notes pose a precise question. 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 <= 2441; 0 <= a[i],x <= 1000000.

Example 1:

Input: 2383 23984 635727 771183 538245 942007 273148 62704 741371 339983 401208 107913 424838 274982 774138 301394 800539 381785 676610 103388 214612 772611 318608 859120 747403 681157 153374 84104 978724 547432 343770 142334 437568 154509 170992 523533 683095 935994 118319 193638 735114 390668 830059 585432 570476 782720 33545 510908 640656 903585 200719 909316 652516 14044 782113 376726 514137 189106 520705 903614 993368 991604 236380 546212 531138 658535 635743 904474 553948 484216 158794 338137 447059 61365 809860 181792 318588 956536 932831 56985 470528 155718 98244 310596 12012 348139 51059 861218 625126 345042 854944 424145 19647 263136 460297 643012 105098 713648 985462 589136 321220 62284 557262 441269 703286 903630 439614 965568 427113 368426 502346 921814 458905 928762 185552 97597 724…
Output: 1435144

Example 2:

Input: 1602 806095 414017 55195 877253 649031 316510 655764 777516 452854 905044 243519 564025 679397 956069 937589 784210 364601 682419 38059 844750 492255 318436 845150 947436 968673 583841 925564 648465 305395 835686 419417 185643 516574 851170 715000 462841 647101 107769 99353 12804 480366 385629 313924 129976 905760 612570 349551 610540 380120 220712 481617 970345 617667 885486 783945 948491 902535 375828 595356 638035 333509 51188 136143 683048 307953 242966 805275 56599 64436 647467 400387 873583 254024 838056 222928 365652 681107 37919 539534 311640 244006 533987 999129 886427 187466 481715 390422 579843 644826 66315 353414 590649 977 64556 761579 74443 536745 482514 103336 843403 448226 959754 370954 211475 597464 904379 592793 975172 511407 172102 775277 843536 977153 471345 383060 1256…
Output: 643159

Example 3:

Input: 1163 309218 686265 645992 56814 333145 77383 402886 638923 548331 895450 362299 353105 726682 798863 581107 237335 802852 809485 222111 580907 306380 464356 460767 166758 751020 964362 899512 822111 417021 558880 108388 990126 502660 263937 705875 796701 3990 714699 349543 745456 670579 762715 925829 755469 726726 318536 161230 197489 315368 377174 202710 299953 718903 211295 591184 369896 931167 938617 150457 508970 895251 16782 365891 883434 979331 657705 413374 933736 29488 855839 587843 460637 644462 922540 931366 836679 785559 508250 155554 501165 106840 692901 304628 926222 628772 88417 983686 125447 479282 302603 913613 772020 391427 672975 902894 605467 544736 467084 527258 828809 396890 383714 283077 701013 708829 997184 71511 263633 170866 992406 824827 216457 364953 736690 57631…
Output: 333452

Constraints:

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

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