CT59267

Ulmar's ledgers Disorder Count

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Ulmar the auditor watches over the archive halls of Scrollkeep's stores of ledgers. A careful computation stands between order and chaos. 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 <= 1646; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 1126 684862927 229869771 365020020 899609683 214549340 966230712 761659726 446898542 387775784 355008385 157014386 81790766 804913262 770920379 634252972 530135767 889579636 235524124 646174104 512663138 771491954 392655996 322958232 730830013 982816742 592843673 947647303 897371535 283092965 796935848 864686004 657813151 807364794 118830537 170200987 329635332 314316772 254181324 332360573 482655815 922413360 705825027 653657280 805066554 933353319 875790261 43942126 750664548 341488407 744844778 700177976 724844926 190715078 357054083 680478871 122760305 755918527 299706736 535696332 634844142 138947909 80435046 387956771 247973451 934966877 226916257 836654196 995835957 804613083 392187378 881640449 264714251 368534831 357787024 522830348 614758646 855167660 309185095 113145216 46886162…
Output: 311263

Example 2:

Input: 805 785008956 682638760 719362561 954505279 962060913 917934527 410509577 506110300 320971357 683160738 377008224 378782664 372471861 194760126 660535300 588049257 547124596 571844870 245983331 965356292 641985815 907795284 782776341 557900312 263076652 169859308 93898260 767249209 442861928 665624581 255656586 128299387 772370418 537359177 17680753 137288651 959047663 956917426 18016780 216098381 580508873 983971593 550374373 812116089 664585225 47337489 545972598 954358949 406768672 64378725 225752539 78030288 144787403 983481315 156991598 129448390 682785287 347910933 532793423 781464009 137213542 340137765 302972421 392836031 322004034 588799720 695709903 646045630 488081964 175402827 178122215 836240100 233341532 203944504 841053526 706436765 791621876 446583087 368939466 797600199 78…
Output: 165755

Example 3:

Input: 1563 611928033 712275955 19256392 45871572 322319695 553946566 903147544 316247397 871746200 952881647 242430514 715280215 888452696 277888431 594814239 503769267 199509162 394622255 939276834 772977273 973123974 710500239 965053488 961391574 403959437 637323767 862613085 348925778 840753502 496499036 437344294 313808658 726609897 416946051 438979258 195385386 591758141 631254792 168049833 83369307 509260412 270467220 482423777 385352443 923707379 515444245 600423732 67945021 630848889 874732834 866928409 589939100 999415577 573726299 847297904 368570507 893857324 634346752 335331189 75330343 431647788 122819646 264796512 268039442 898091085 602592131 682252128 460767187 996920742 406044104 984709167 890003645 887895158 804301301 600087478 10471438 344135331 561420358 242904840 641441101 4…
Output: 627886

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Ulmar's ledgers Disorder Count - MEDIUM Coding Problem | CodeTikki