CT48545

The Disorder Count at Scriptoria

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the ink district of Scriptoria, someone must audit the season's records. This year the task falls to Weaver, 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 <= 1158; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 180 135 113 75 23 26 45 116 152 111 85 6 158 178 55 36 39 140 59 123 66 141 52 65 33 154 9 149 96 163 76 153 80 173 14 156 48 40 22 70 68 83 102 177 117 78 136 21 77 114 137 164 25 79 109 170 98 107 2 43 27 129 84 46 51 67 146 31 93 179 41 101 145 103 91 125 97 175 47 100 24 1 161 133 37 176 120 142 10 171 63 3 56 168 4 86 138 124 0 88 118 144 29 155 28 30 157 169 49 7 42 64 132 50 61 5 44 167 11 115 131 108 20 58 38 128 119 8 72 13 162 112 18 90 159 151 166 74 81 104 71 32 110 87 150 127 19 134 174 95 92 99 106 126 94 82 60 69 148 160 147 89 122 121 54 53 172 17 105 62 57 143 15 165 16 139 35 12 73 130 34
Output: 8053

Example 2:

Input: 692 190034867 471225498 203396127 248121963 160203436 579251296 973595951 712326413 862554200 707143519 777824345 466780755 323100187 886080272 387915089 21076203 837819493 265104627 48043569 14655340 890434090 91592032 809647052 549770217 679671528 675289715 665205119 538429788 514440938 8043707 5196518 602569754 881812390 122788796 703827697 97599553 452062593 743576483 812420531 150830824 838403276 211337383 592442058 970676703 697006295 903409375 640150551 730860427 633263809 733540999 144133253 55302656 409522877 710133337 937303526 921466226 659345444 426876135 512672347 168396847 30988146 261296315 266840532 951275155 749139614 93077059 730578082 658444736 740330450 490003666 105481445 124823373 144237515 815807049 752255726 585257004 352721931 214625355 337438232 928944763 31941813…
Output: 116985

Example 3:

Input: 1157 44 297 994 190 626 1080 759 751 993 861 1021 244 279 126 150 393 848 1066 207 308 306 875 149 587 445 591 695 611 451 158 83 915 230 389 887 212 15 982 1071 888 123 354 520 530 549 182 811 47 523 259 605 593 674 108 14 0 502 548 755 498 21 820 600 322 843 750 977 74 968 902 948 196 725 33 1054 973 427 765 340 28 409 898 1155 892 189 663 408 1038 461 183 885 710 462 57 118 631 859 1143 776 568 39 745 1047 1020 67 979 1046 141 1122 1065 640 827 986 2 597 654 835 49 344 385 1058 177 215 981 403 416 359 225 367 271 438 290 286 1027 372 69 31 129 1032 954 867 301 583 426 454 473 833 823 288 984 1011 379 418 331 449 1070 643 324 909 56 509 691 974 524 676 204 783 307 962 32 1000 313 844 402 553 661 934 692 665 669 1116 818 191 208 504 613 361 858 687 749 471 653 1131 1056 1123 274 1150 978 …
Output: 331413

Constraints:

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

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