CT61758

The registers at Rainhaven

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The harbor bell rings at the monsoon port of Rainhaven; Nora weighs the day's registers 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 <= 1433; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 683 -626785 223488 -917486 -513505 -483654 -929781 -848515 -121014 978591 294308 -749784 -108764 980068 -878387 -217544 -930648 768635 -979215 238995 -780655 -170942 619101 -458267 -739349 -892454 -927480 -775306 -402116 -986834 420756 796092 908048 -292782 -610758 -507733 4513 902244 902685 -391330 770200 531842 -933584 22483 420035 432551 -425946 -565992 -204423 888496 -193674 -72165 -566501 -249748 255673 340859 726410 -212874 -375658 -361128 -696359 44370 280522 -7615 -918298 -40514 798332 -710892 468176 -770570 135468 988523 751641 -745990 -58295 475973 -607613 -22998 -754116 -973818 -410197 535077 379516 238325 -335289 347264 -4044 -801664 290035 945030 -416739 -503198 376493 -326057 -80284 120541 -141093 836383 -69664 -853271 786192 636869 717342 -119938 729114 716826 328141 -135357…
Output: 115409

Example 2:

Input: 290 252 63 90 123 202 93 247 31 221 32 180 116 272 83 52 196 28 245 8 55 224 197 242 277 198 206 267 86 179 96 288 59 61 154 204 251 39 273 100 280 226 230 171 94 57 0 183 172 259 213 47 16 147 20 232 155 145 248 82 166 103 135 222 58 70 223 189 269 140 60 158 102 257 120 37 286 141 165 229 51 53 23 241 194 71 17 118 142 76 134 199 127 212 48 191 281 30 79 169 104 243 167 133 4 2 207 208 6 237 182 149 150 234 21 110 289 13 136 240 84 24 115 244 12 186 164 7 128 50 19 253 69 9 64 45 33 139 91 159 95 62 88 163 107 108 80 75 3 184 34 225 25 44 156 233 74 121 275 250 258 38 125 170 5 274 92 287 231 111 178 215 239 152 256 270 99 87 195 77 106 175 65 10 265 283 255 101 246 97 138 271 89 85 162 176 266 27 122 72 67 11 210 144 218 114 35 113 42 261 49 157 276 236 124 193 41 249 66 112 228 78 151 …
Output: 20504

Example 3:

Input: 479 25 198 401 95 1 187 122 365 120 121 341 176 19 128 207 185 49 76 406 131 454 143 78 146 473 36 114 461 412 39 2 35 193 283 432 113 319 211 340 169 217 170 284 203 124 414 181 425 152 382 33 70 257 368 448 271 69 332 157 438 75 4 54 364 91 115 243 194 273 34 348 27 106 87 16 407 224 52 105 261 94 98 177 420 379 151 22 171 116 456 188 322 62 71 212 236 377 3 306 141 451 77 464 326 424 286 384 248 231 443 175 11 235 221 311 223 56 301 280 46 478 178 110 387 210 26 140 325 453 314 356 218 160 399 129 467 396 292 12 392 339 367 359 357 429 342 395 303 219 92 465 360 83 449 403 234 168 132 373 435 6 426 227 82 228 307 256 130 155 153 147 250 142 376 431 394 436 318 450 468 100 460 264 123 10 79 199 17 252 328 372 317 42 232 477 37 346 338 275 206 84 186 104 154 441 294 21 192 242 447 240 85 …
Output: 53809

Constraints:

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

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