CT36766

Potter's shelves Disorder Count

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Potter found an old ledger of shelves in the observatory attic at the lakeside town of Mirrormere. The margin notes pose a precise question. 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 <= 1077; 0 <= a[i],x <= 1000000.

Example 1:

Input: 947 594725 812508 106322 575253 694600 473620 957880 426817 467729 464615 249891 210417 594772 471805 24547 577113 250587 850617 938198 151315 839628 449840 61321 461981 474226 144530 861940 858489 295001 515357 621783 823938 371301 997537 6801 76284 89658 77795 226971 75662 935084 196774 472313 973085 251693 869543 141437 448704 716639 973368 536397 795048 607590 985917 628160 199460 993032 392481 515121 853447 128474 902267 329474 304224 843495 251019 228696 226570 204018 310336 23849 752690 128718 196881 135587 300856 568711 71117 590613 274454 647206 762084 556487 957542 909099 551276 472145 34780 964035 972592 354914 274973 204627 273424 203621 239105 709579 91753 52125 742901 291916 782519 142007 281868 56223 888988 254083 480357 69023 714902 266096 204639 553578 232925 174035 505136…
Output: 219649

Example 2:

Input: 503 323333 765336 894629 422525 652420 909387 578542 477788 508332 510442 755330 725317 451166 926466 263677 959689 201046 893662 565653 371488 213325 296912 660053 551698 491746 589983 175391 522106 983276 933103 695409 869875 722099 933829 230837 522209 182618 123305 192990 324187 265156 694617 829102 833075 329300 967743 100488 447147 623233 575184 750991 927972 279911 408333 739658 262661 60356 513929 700380 700586 300805 407082 392982 205617 975299 48579 861979 862284 117031 899254 874200 732673 856209 462528 914018 366323 5076 124906 34770 353681 721300 312853 782066 129301 859358 266018 199184 354992 773397 349654 578794 2357 755155 342380 290164 982697 336243 896310 272702 844918 892289 2739 173616 597196 56876 218178 955586 306465 352909 943895 748766 604594 585475 335653 294104 6…
Output: 65980

Example 3:

Input: 275 170 144 141 258 193 130 240 216 62 146 124 212 233 126 236 133 139 241 191 218 24 234 189 196 107 34 53 220 25 125 95 4 104 105 207 225 114 122 111 254 131 60 243 115 174 183 31 97 229 137 65 186 242 156 127 135 16 123 90 54 76 140 147 176 237 38 179 267 262 153 222 249 187 247 157 5 272 161 121 238 57 261 163 217 257 3 52 17 51 67 106 165 18 110 68 201 172 188 160 108 250 246 244 109 1 119 22 28 149 46 55 32 19 56 85 42 194 64 154 206 36 195 171 209 162 184 263 224 78 231 266 94 39 102 226 270 82 265 8 45 101 79 11 197 117 232 159 190 81 113 164 99 86 59 9 227 103 63 83 253 21 208 158 37 178 7 211 152 116 26 214 15 75 230 213 118 204 169 89 49 259 69 33 29 271 264 219 98 138 128 256 166 143 192 168 71 13 47 274 91 48 129 10 203 198 182 0 2 23 72 150 210 245 273 30 155 228 100 260 255 …
Output: 19944

Constraints:

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

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