CT57260

The Disorder Count at Alabast

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Every season at the ivory gates of Alabast, someone must fulfill a tricky customer order. This year the task falls to Ivan, armed only with the shelves register. 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 <= 2600; 0 <= a[i],x <= 1000000.

Example 1:

Input: 1634 591778 957981 814476 671655 885719 294708 328523 662683 376290 856862 329021 336226 816932 903546 206261 883100 621660 100053 921877 291830 916596 646552 262167 398866 452112 410692 433688 915751 443662 992393 978919 698520 4701 787230 874347 541301 31962 256296 786426 585864 349285 794919 387396 599718 527757 194360 896566 26711 904562 351432 98867 621450 211604 628963 809156 333199 289489 540588 212417 565768 303006 773066 886995 196322 951198 566890 407631 726345 430585 412380 487197 493388 650554 883095 4371 671140 131353 24832 759363 9952 459596 308529 6484 300151 894260 6694 825681 166208 919118 542063 321707 420863 469214 958710 564909 721088 729756 931407 231320 771538 723972 90801 514121 257037 339569 584169 339419 68460 323976 700824 265682 712616 916235 111254 970046 977103…
Output: 675178

Example 2:

Input: 308 961181 466220 116387 249269 384295 160546 770046 153344 387267 910787 916881 545313 565021 259880 449643 297073 695576 858635 32199 10430 733501 159425 107313 202387 868688 582702 972471 74902 983570 57624 20813 281574 119161 670865 873177 268002 93029 101442 297803 514750 828570 679664 166298 60379 519091 931287 795436 25105 699175 244706 636852 303881 165495 67357 725922 800086 624904 195335 425669 432337 95507 914022 305823 497881 155918 925657 573632 915496 369715 200449 469005 510281 133736 237874 161928 725180 816571 465961 811835 552576 659403 887833 138043 6368 387928 335557 292247 671859 567584 433597 70735 742586 191300 871107 640997 812023 316559 503904 891800 996709 425605 434290 136153 832657 347468 586163 586724 483179 269358 528830 491494 546074 794086 456218 252086 7403…
Output: 21739

Example 3:

Input: 1052 318620 205707 21049 20698 561692 220072 234140 660076 225817 44403 365090 162629 315813 471508 112272 434692 976345 94296 368055 760931 54891 902318 391351 251662 246809 120813 369928 859828 941477 969353 721445 627201 814060 318749 140681 95371 961122 668625 781420 932514 768280 69333 481886 90180 932292 727775 145755 915185 455506 301012 590620 199716 962849 92617 266935 124714 499509 842876 637924 849735 816056 93096 668053 164918 5625 305932 832590 209857 484742 931164 961759 546423 207297 185991 371999 646159 60103 751863 51167 12785 732155 888454 283995 402306 157059 123231 258966 40585 577245 252781 728307 163227 185064 339606 173223 908892 265816 382838 430831 26553 543681 663572 894167 260830 523668 971849 775987 453646 343749 238504 483375 574083 623183 328022 144378 320992 …
Output: 273333

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Disorder Count at Alabast - MEDIUM Coding Problem | CodeTikki