CT62839

The Disorder Count of the Sterling crates

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the foggy moor of Greyfen opens only for a perfect tally of crates. Darian means to find out. 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 <= 3117; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 2669 525412034 297911376 259168941 6298815 486033110 797415916 746045845 793854430 114861685 609213255 341030686 384270625 544059947 435379605 493092413 91762870 206599953 111659562 393932148 442418722 922743134 830788541 693980941 429010033 530905779 769013155 245751754 513011076 615845222 428501284 613945940 969150540 167693114 590514546 474801890 764385862 770220152 440227830 268593618 771702855 602650268 657624308 342380268 846395175 990766012 295322787 558336124 240020205 555734548 189022913 372484723 393017661 852653698 575699862 511911424 241948187 35950012 145329004 308596622 373587594 170684360 54773590 544031015 397868498 957389737 480987615 4397914 71196889 158701860 425108634 243565749 989665197 739090267 581931071 17614967 845143920 15878464 249374375 550169370 505483808 31781…
Output: 1771936

Example 2:

Input: 547 543706119 874782772 626655970 237013445 770053530 723207090 858271138 990197099 89678985 142565974 702785477 74441762 172827575 578851779 520790801 676215399 163112275 193981036 293567232 881514321 885686942 358134864 485515933 60754286 33062778 169952272 98301894 352639089 800812091 556924066 207157323 35083751 210862791 221200240 207288408 22429355 92004486 454235581 801630184 975806488 454724700 849354392 640236072 522146143 153492336 731914901 395200098 766340762 16493492 635694976 542434400 276720934 635175021 660455238 248497943 524331406 210480014 256463521 462952552 120786680 368474849 714055898 203962735 396535592 728318432 861736575 831866585 25893284 363219711 417544222 176348519 356329104 245568437 677714449 850551448 493813149 674774865 907088073 536253496 441063584 398235…
Output: 74879

Example 3:

Input: 729 475905036 451717793 284415488 985297100 807925972 605417397 585011392 42357076 180901132 354367162 958826242 129324417 993458792 592947536 665955073 117931805 47200165 415436446 951676750 968175620 962133838 285289758 50426954 902233229 479921820 81357656 644327874 233839220 644809083 535681241 305493888 922771406 151861999 792963581 502226475 448862128 672852334 332107136 619841524 284283240 261149676 623780923 428093027 153224521 16819167 919152996 572504998 851755739 110377771 418671440 296871142 333729719 947266301 397585735 277769910 104970780 395964567 353579764 725968934 912427712 132049753 235548888 419746443 506773509 681535429 290730980 710028302 333114541 541921600 352172107 425681019 302282203 751404146 674522777 714292503 539059768 960058715 586585432 55899318 72689794 236…
Output: 127856

Constraints:

1 <= n <= 3117; -1000000 <= a[i],x <= 1000000000.

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