CT58537

The Hidden Disorder Count

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the quartz ridge of Glimmerfell, Tinker records each crates in a worn leather ledger. The guild wants answers, not guesses. 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 <= 2767; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 1015 241 466 21 300 565 410 234 240 347 180 239 943 562 809 579 594 138 377 415 556 315 786 192 361 631 589 979 844 857 741 97 413 805 880 61 223 426 546 26 144 1005 333 795 306 474 74 383 305 645 883 629 111 513 886 520 1009 710 119 445 962 91 423 188 498 395 961 709 574 970 195 972 462 533 661 116 349 398 810 830 356 46 785 988 296 393 775 505 295 714 7 705 106 509 268 149 70 122 81 730 872 375 758 616 424 145 153 288 62 932 379 623 602 639 307 527 697 825 493 908 890 753 843 217 712 352 208 372 401 829 967 686 879 84 561 385 955 202 109 444 151 703 297 485 997 471 634 123 868 459 755 449 698 1011 973 735 465 19 265 87 845 370 528 230 378 412 86 407 673 752 954 928 402 993 345 340 841 203 37 828 514 725 219 416 384 495 127 308 781 784 178 893 625 47 889 907 540 737 659 167 343 648 998 53…
Output: 261474

Example 2:

Input: 1205 166 350 792 974 291 1029 513 238 1191 816 831 565 803 622 497 137 734 824 910 1007 124 821 604 517 336 1194 4 598 40 1043 94 869 1066 272 1159 820 823 872 461 9 318 406 555 536 1086 608 135 379 44 699 1046 1106 1016 280 108 412 753 212 49 1088 702 1130 414 1148 1089 405 736 2 1197 899 658 861 902 588 477 1004 372 709 675 744 86 69 1124 867 663 1147 739 1015 582 320 577 270 1024 782 153 674 269 750 425 507 959 773 196 606 747 472 12 759 572 102 1101 574 361 656 692 382 945 261 1112 654 838 314 903 7 48 39 535 948 938 55 914 657 426 665 1041 400 422 890 189 630 266 714 440 725 216 1045 46 1200 583 1102 1048 76 68 139 245 1052 432 368 140 589 486 1157 518 1111 1107 218 249 356 560 112 3 514 288 396 21 337 854 281 217 677 97 629 5 47 1078 1178 1141 609 431 566 333 23 634 395 563 226 191 5…
Output: 354826

Example 3:

Input: 108 92 71 6 88 13 65 15 83 49 18 0 2 105 77 74 48 38 64 25 19 90 8 58 44 12 57 10 59 95 30 66 104 52 42 17 53 81 3 11 33 56 36 107 29 98 26 21 99 67 102 62 60 100 87 28 41 39 79 32 76 78 24 68 9 69 96 75 27 86 63 14 4 89 23 34 70 16 54 80 1 73 43 101 94 51 85 103 72 47 45 22 35 20 31 46 82 97 50 40 7 5 61 106 91 93 84 55 37
Output: 2692

Constraints:

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

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