CT50133

The Disorder Count at Brasshaven

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Ulmar found an old ledger of registers in the gallery attic at the old quarter of Brasshaven. 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 <= 2736; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 745 954937659 454349726 493598767 759865169 818500950 538169534 915515334 136548137 952135491 893817544 401150016 317906129 126284711 716598983 716824659 949650874 6207204 946342899 446928108 414290001 190546477 423155165 844815847 200578131 881883209 920392594 54441557 722833970 956662065 739916934 225662234 278196242 759767515 232947613 93272819 641002808 244896583 655079720 399549007 908398953 982610383 305441811 887525766 534973437 742605227 540656708 599264836 632494056 130153187 314151006 792461796 151297824 88267280 120919694 906369688 116695519 126559324 237416606 681470473 717727025 365033812 489725376 97181247 102690410 514731593 737183524 744668473 803899755 97401950 932029831 552248075 921649259 537632930 500178097 415856195 749188000 44211612 71226201 442383193 438093171 17930…
Output: 140581

Example 2:

Input: 2282 481513815 429753260 831354491 322490982 780198361 362681308 521653856 874738453 358097868 266477523 396904626 932924421 648647790 605481758 243916648 873510946 228469922 839657150 874893494 485913092 52527740 976917693 487439548 954160586 429459006 419822155 738259353 480823083 607205987 888234328 358165191 111935865 141938697 473733577 158671828 552216753 124839847 447547328 487074997 486538281 676807863 174989853 982290017 729549295 453128304 911899761 430346503 842585786 655497303 112052745 842355062 42816627 694614618 149070292 733664998 179134368 679759449 757235027 619534348 84204784 370570405 644977692 340482087 312746653 542774630 821761632 641956282 269293246 727621956 41189590 976914033 886503328 409052947 508570218 525895896 766006789 949057148 900867864 149811160 348018699…
Output: 1318654

Example 3:

Input: 64 14 13 54 0 28 62 2 41 3 44 42 43 31 19 30 25 50 37 52 61 17 40 32 36 23 22 47 11 6 24 45 27 46 12 39 15 49 7 48 35 21 4 33 38 9 63 5 34 18 59 51 16 56 58 26 8 55 29 60 10 57 20 53 1
Output: 962

Constraints:

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

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