CT60836

Last ledgers of Draper

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Draper inherited the bakery at the acacia flats of Thornveld along with its curious bookkeeping system for ledgers. Time to make sense of it. 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 <= 3048; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 1449 932933010 549873015 224647235 29665239 161061089 37998367 567265966 42324655 561522739 970222511 262432810 478395737 565746258 388912301 682466321 240364194 443177044 898174326 409254200 233360002 417264776 33767695 284577051 194272594 931543994 725370343 576807313 60550908 904353720 33321541 165076600 437196315 168037265 969465798 189149380 259234089 276852866 999145035 122214202 520431229 379679980 63535620 811754708 563486612 409650637 21602461 905467493 106750213 413942664 124090364 525629972 153055852 964969084 490691844 789011393 440457121 429598011 620283292 273195740 261435881 932949873 751962235 182804674 776612841 87943016 788232706 700128990 123843502 355787832 261158648 669746915 37875257 949747895 331350002 684177614 123128457 520559801 466395223 596476696 574196158 24569…
Output: 537315

Example 2:

Input: 271 671602886 430781857 780928578 813190942 568189317 117360270 323893699 498198856 269195173 138579010 736439893 190033335 293894823 91482780 235391048 392042960 302894356 384171042 244163181 223569627 24454303 775736658 765692241 132550183 649739051 300037140 25550999 444250222 767376630 662651666 129797004 75278041 406354073 668401771 444813433 989450731 695759074 590456969 65181011 250636122 283025680 422875107 701481105 275548440 687799140 407167257 616553544 310828582 268159771 975841317 851646458 262141148 112278520 143998721 445556378 473621374 666462482 297950297 776967124 399381059 626943294 513716852 802964847 391288873 127237345 786127815 662724707 387934924 878165696 891539412 85158909 633411470 234123327 101758372 577003772 771483387 14706402 561132378 532450430 424092158 838…
Output: 17466

Example 3:

Input: 881 657784014 969636254 311382385 460313089 856593599 648233649 866607997 422085391 128133157 309379627 570408425 253553305 944683604 939755073 575867971 582287116 433639339 849537338 158598583 705465640 549389947 491770007 952826660 166192958 45781242 764729804 805124550 48079134 500591719 112667321 508305990 98088821 485808054 914285695 239002645 356981837 23140831 204808102 584357251 84759544 77417395 762758065 571138096 856719410 319578203 690692922 568768696 240814072 787582237 870406917 80672530 22311359 443058998 495938324 382778973 162246050 544998808 606681765 686395279 820374836 705913078 753395943 443841338 864248174 220101046 830533839 678215216 808584789 653622510 116340356 644931241 416531154 361270963 901832646 640277932 543493330 571226446 325935026 280331990 493012210 6127…
Output: 198348

Constraints:

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

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