CT57799

Zoya's crates Reckoning

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The paymaster Zoya has been asked to plan the beacon maintenance rota. On the desk lies a long table of crates readings. 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 <= 2826; 0 <= a[i],x <= 1000000.

Example 1:

Input: 622 265137 256150 924961 645395 189530 843950 496252 847018 298835 59942 432065 128595 974353 891521 595492 595222 193010 445853 990518 803502 980210 853522 730146 362179 481011 711080 713881 672412 587368 384890 601119 347674 627630 468235 273605 195075 507399 592895 128223 763635 895772 244835 434141 83691 79475 124986 473016 689813 797095 499499 164489 276252 899930 647779 546074 342412 374723 517619 21213 689824 662 292424 318145 463322 400637 241196 881746 793936 385047 209479 898887 171378 479424 264764 979490 391535 97763 57551 968195 769981 290433 721799 561047 518385 351714 450228 490480 617498 104847 610985 759615 476390 170593 888266 506419 426865 893641 941924 425204 823210 869809 50569 414833 273715 841045 64646 431050 921876 904705 73765 455864 836027 712914 620203 764034 272…
Output: 99189

Example 2:

Input: 2051 28340 299735 924433 893065 42290 368671 350463 134759 749282 79599 94778 777486 821856 204612 32990 446429 827162 504571 20327 570852 596156 97395 338187 442230 853195 456099 435136 384124 717153 965422 147205 145947 772427 941664 760035 141645 285922 283875 612878 707039 510996 270132 441315 187515 842895 750393 374237 646767 15126 151917 449902 644810 100027 150269 883708 433566 348846 488010 468841 135795 300435 383166 721829 541280 855463 669257 563139 652824 755317 660941 71462 487361 869057 373043 947977 26956 333097 644652 27246 197693 395920 256183 473619 370170 650265 624054 457815 953069 763401 154888 200922 883784 237506 449984 402775 816671 96071 571377 209730 564155 176809 23577 958981 731132 525245 888391 353361 537322 791530 769008 821677 701009 977701 148353 402085 233…
Output: 1040191

Example 3:

Input: 623 788221 453498 39713 719101 392887 694678 280674 831956 439113 417249 62549 553389 331530 537626 434779 884747 441914 449695 983741 624916 831956 80379 991563 68601 611801 225714 990778 934094 517868 591886 503590 253234 227617 155162 601600 917710 600932 233597 952049 115584 643706 249215 231836 26304 289413 126295 103203 447101 60209 5355 534679 378405 104385 60054 898983 815767 347441 691522 595982 993468 99672 131921 429214 14368 281800 841427 644119 465643 678680 437033 167742 168780 93605 338659 630827 674396 770826 166798 739178 983608 967560 987088 10362 77336 834915 211751 366951 671156 633130 405819 383187 287833 867284 668153 295417 737414 668179 101625 118401 322483 514879 90960 98588 965787 275477 872110 97581 970909 571582 653518 690852 748957 32759 235092 109717 394255 86…
Output: 95115

Constraints:

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

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