CT62093

Herald's Ledger of vials

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Herald found an old ledger of vials in the gallery attic at the acacia flats of Thornveld. 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 <= 1775; 0 <= a[i],x <= 1000000.

Example 1:

Input: 649 604136 818098 306641 365447 80648 200815 762025 993326 793112 240361 326520 231705 916823 438464 156007 984545 673093 135915 741436 687108 882896 989353 956672 970140 712040 245745 271894 363748 973220 177388 893701 890598 529896 250262 49797 509293 620057 725348 260349 227665 10970 159178 140890 346088 137742 909387 115023 724716 413813 664851 508156 458052 27514 62670 648240 655673 239906 769640 275305 34615 571852 738243 418652 146858 416227 867293 120668 856473 235692 200729 726992 490194 413190 216650 904791 308298 854477 926255 251035 543927 786189 541194 732288 515967 546933 675402 631273 688546 810968 283720 964052 295109 736597 659941 208554 532918 59340 149033 148247 498060 541005 191494 473676 633647 588870 909726 800893 698481 146261 142041 316312 206273 643012 172741 76384…
Output: 107818

Example 2:

Input: 1411 337098 115449 594885 66770 834631 718421 846198 374539 210564 431750 521793 101404 374984 741288 484222 810594 109207 905755 49028 924343 734981 387529 416480 342865 723712 789841 883811 45784 497523 645851 566405 246122 817593 703582 405760 124498 508474 290690 699198 557339 340287 747890 529824 557959 247525 607630 375087 986804 141631 540995 181974 389700 161921 148448 246493 70791 202741 309230 251338 909314 567538 908229 153845 260388 873642 254563 786231 113590 481423 791445 757869 327041 418898 129870 173566 379315 319473 540844 958982 55582 674524 965202 70861 340946 29475 681020 486413 228193 326364 779786 244601 203168 14325 438649 413039 689504 496759 525200 666158 340090 248797 622025 585555 998408 711668 222641 472106 887044 985631 660501 218012 447748 824852 925516 18169…
Output: 500892

Example 3:

Input: 1589 612543 17632 132116 297310 162362 547010 639126 205566 656578 209371 239327 513232 54750 171116 183605 352701 269320 559065 163836 176375 269574 724916 96738 191222 502082 997056 363473 627494 744362 175279 33255 907821 526008 954588 962540 838657 850955 579753 818377 542157 198919 174310 144877 188290 35212 193065 604988 879882 328246 61568 38251 620960 920357 986286 376466 58072 743884 903246 505482 888720 742460 418190 40487 515569 204304 435749 484615 476351 409983 450910 20341 602664 868315 745899 459134 32887 985613 378442 379729 373934 955790 216682 173628 146148 427162 522053 184884 510746 439702 714843 191258 675340 232983 702343 61924 261484 476542 948518 312511 617715 170203 322193 762947 480423 537384 65011 502693 688085 733217 314785 419051 136785 841798 660473 63907 2892…
Output: 620467

Constraints:

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

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