CT51665

Corwin's Disorder Count Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Corwin found an old ledger of ledgers in the brewery attic at the windmill fields of Gusthaven. 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 <= 2783; 0 <= a[i],x <= 1000000.

Example 1:

Input: 1029 33894 685292 546419 948000 350699 110434 17755 531905 905995 605626 645070 321229 313032 494350 861168 626986 191586 826789 942875 857832 755232 5977 277369 128996 36265 861420 246151 989511 686701 422392 883796 148507 817854 945068 73511 185324 541714 738074 717551 447929 630898 352046 715864 673397 824519 668099 469968 884164 57087 788204 570852 714372 670128 753560 460627 97581 469925 195813 441056 990051 290254 637880 237717 994173 296620 149487 834428 435122 215622 789062 307095 325728 363635 902872 132613 989093 785368 792662 622467 950934 349359 567405 424222 165787 451346 921029 174857 380511 716020 342559 980646 208695 929963 422669 429428 316795 893753 126380 881601 30503 61961 564640 918985 232726 180144 863526 608478 622646 949167 108724 695398 899910 419360 244261 14014 8…
Output: 264020

Example 2:

Input: 1724 369015 621967 781000 328705 109789 236655 184031 777045 279455 345239 153674 812215 301880 442435 970727 720035 903565 878546 72225 57918 678681 428321 555449 875324 510708 621807 838412 447968 255485 353999 183728 789413 668250 681654 389676 323311 192093 958267 519303 80468 112166 529889 414148 113805 942204 650101 150737 446357 277924 10767 269080 65486 667708 375720 828736 926372 639755 665118 707489 760729 448916 231777 630462 572031 319118 114126 985366 521798 458358 6747 312339 150301 17208 215761 847858 553624 103784 361176 961361 672877 482879 634117 840990 734375 292924 511024 245955 933552 185018 446957 993393 479359 43864 687299 235374 732763 292204 155868 480459 887994 857100 193535 933023 163783 530265 18529 564196 112185 811948 144641 256789 266557 461208 598882 454045 …
Output: 742220

Example 3:

Input: 1387 552126 58819 869551 98407 208609 185426 642526 567089 455067 880313 397408 99204 358204 101309 945686 290774 922005 264980 625372 490251 706182 837485 327094 806345 25029 538287 111565 658155 711697 328549 379447 366043 108793 419017 826897 36615 537448 900091 721828 820895 996560 73397 431845 87067 779781 877558 564995 120556 837000 530479 692674 543454 586674 749538 401899 102954 969306 688051 609532 626566 749053 597450 155912 645616 334543 999128 699808 148016 866451 102324 575339 352294 221808 926531 965147 457761 235899 613285 926128 711181 861331 210923 701156 430963 843801 534251 292176 474300 612866 335649 691653 789734 764631 996352 87590 32917 303188 561423 670311 370393 487501 387007 28738 246337 264808 450488 43889 239493 348966 314148 926283 853566 719917 966847 821598 4…
Output: 475493

Constraints:

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

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