CT63825

The shelves at Masthead

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The council of the galleon yard of Masthead pays by the answer, and Seth intends to earn it. First: the full register of shelves. 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 <= 2145; 0 <= a[i],x <= 1000000.

Example 1:

Input: 294 57721 381025 697889 817101 949782 963295 567544 663253 561418 560427 699507 414530 854830 366861 879211 752049 526480 342538 492728 868983 837029 372899 555812 425190 811674 718466 155310 363258 821352 63458 520590 214231 265974 932705 237334 219532 579896 805781 264377 881738 22812 305426 445381 9364 865250 653527 594005 371107 958186 157850 846707 478364 81285 334524 901285 785897 547092 707955 208222 41465 894288 651887 711454 616550 695589 453368 780032 983143 500555 633291 776606 671389 595404 96324 502602 193902 842098 677793 790777 919010 429615 724523 880813 748456 207343 995804 241356 845948 662539 179724 809431 328763 392865 408144 204891 740467 205139 450125 563326 326171 245750 584429 397855 755768 297577 767180 87001 190172 427609 378557 859651 704411 711889 26750 89518 67…
Output: 21962

Example 2:

Input: 541 641364 570864 647323 834343 724824 663018 492543 62937 546214 810642 45034 951790 860069 791960 894203 51236 501796 336554 147076 129644 834904 154406 977411 552572 907657 713577 610588 148069 87609 787711 359978 215423 395538 582429 419278 122013 38582 993683 479824 473356 197822 97542 601196 426875 94304 394836 393592 820030 241378 576864 390359 449132 937728 749839 725198 981619 751244 576908 483123 420750 427899 48523 835352 18424 764031 477922 958356 740247 282969 429534 364959 980512 909441 406701 840566 943149 270338 399706 853219 308195 694324 966487 249190 262691 19391 379546 520828 661193 311769 259593 228016 294805 334157 427295 374197 575634 559622 697694 589105 483787 235183 892607 369417 902995 145548 371024 114846 34816 429876 952502 658624 280451 114829 441626 373629 17…
Output: 73119

Example 3:

Input: 1229 547501 774188 830920 728833 136595 110563 314172 371547 871212 630917 656973 51720 703572 11667 203974 663386 658990 1452 940522 845487 563241 507769 259923 460053 220577 585711 318946 681017 768769 233974 107922 805574 684697 940911 411176 251836 56283 41272 292608 824117 471463 21073 436137 10580 862347 108489 160281 929829 228866 318972 263137 567539 870122 848002 14603 598909 155161 140966 210695 977544 645565 664281 410586 412182 252276 308642 421081 255367 990775 66062 137894 174000 779535 23612 694021 640533 724548 240518 956351 780049 566493 921997 969994 157255 10739 818508 509640 188475 43133 871029 894007 845959 191091 589107 56019 710643 353339 184569 780102 109861 919318 582117 569316 619581 128269 929135 338993 715223 489043 610733 291619 83871 682167 951674 384558 62416…
Output: 378191

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The shelves at Masthead - MEDIUM Coding Problem | CodeTikki