CT47489

Uma's crates Disorder Count

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The harbor bell rings at the cedar groves of Balmcrest; Uma weighs the day's crates manifests and starts the calculations. 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 <= 3587; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 1132 408 398 1125 575 316 624 293 334 916 836 217 1091 125 576 299 331 518 810 841 1115 434 260 788 229 955 163 429 973 1108 532 205 583 301 291 544 949 424 573 121 1031 997 517 201 274 543 572 828 62 1100 261 340 1045 759 719 1025 1014 29 259 657 1030 161 1120 845 554 420 443 1019 540 846 600 67 1063 892 472 504 925 86 872 533 132 359 524 1096 1089 757 268 494 1101 662 651 451 432 425 906 422 523 388 137 431 1097 805 720 433 239 480 1057 753 1070 326 297 405 177 273 766 655 1048 57 271 705 313 534 298 254 982 1098 993 108 636 157 38 43 770 423 58 1034 250 1010 1008 227 860 819 584 492 35 792 732 468 806 103 644 182 253 463 347 20 800 606 228 193 569 547 603 317 115 349 401 986 692 170 741 467 947 570 977 551 126 875 693 514 595 1075 1112 147 803 853 1121 21 91 776 453 642 1038 194 877 330…
Output: 325064

Example 2:

Input: 152 486264886 234397163 12351049 429809788 178730 93534089 647403334 297715825 742063640 978790767 956116942 612319591 114457424 411557533 794052330 555035053 137971121 723628211 421658941 524717431 157149829 501828598 955138433 757640169 85810701 723429485 699805746 984670608 109475397 619303072 246575690 923108749 440561568 472654171 383591454 703119809 92445358 224390775 675240567 219887356 234372064 72291502 368915216 821688442 46072596 476596916 799471353 82080908 684376909 565204282 569587691 894853674 17933085 552028168 290911432 497759150 893537432 847815580 300959665 636635269 614363271 171634374 272788219 917024058 5625422 920159556 949353132 608164237 532225613 512096731 702299265 891868141 923372230 579020705 24708721 158135516 927153605 945631711 313532440 86945083 397836205 1…
Output: 5560

Example 3:

Input: 3469 766544151 799583466 174754629 726493651 417447136 200783995 40479821 54608747 853138766 9060968 727843845 643490171 86383830 547252193 104237822 9758123 589585299 123547219 655253696 938600847 950566307 688447061 590702292 264664844 431329537 877895243 963022979 140361335 551041189 386623539 135221705 781755327 502772941 939120011 957844716 697619851 627737561 609560169 334376846 666775062 327115725 857953405 492228407 737523984 825917684 534979921 674910832 398348234 823942944 600774951 996355012 599664945 930057478 301053391 949871621 921412903 489879036 207629316 498945135 920347761 270804260 657471255 97988237 943795009 348578851 696636207 557247415 439802791 119313082 665189419 52755533 641567263 361638324 821334355 78637203 715529533 734543614 540507548 927284850 939958333 19577…
Output: 3019019

Constraints:

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

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