CT35527

Minstrel and the Windward shelves

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the valley of Misthollow opens only for a perfect tally of shelves. Minstrel means to find out. 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 <= 1802; 0 <= a[i],x <= 1000000.

Example 1:

Input: 675 1978 640517 975294 190131 874134 20182 426444 444221 431942 168782 302123 300437 933337 885657 64826 619050 508324 354018 890688 281116 922367 648278 986372 130252 816221 583300 704026 475245 451003 604142 87097 41124 592490 116066 27512 858125 44370 67487 916525 207621 809168 599198 790659 179206 586190 80295 755793 402605 341385 401468 471381 388940 922532 267892 540610 441146 726631 627178 190347 914111 647446 301622 818275 976566 675934 664268 689899 682433 643696 635155 361424 54582 137906 591966 639216 37777 576239 583336 202871 974527 354220 702474 349073 384041 75497 608684 70990 126331 835168 881023 539017 953610 569319 294831 252565 719767 142175 432068 803531 188259 191995 90356 697508 751283 257637 339468 869722 303146 663914 741120 90672 893210 12658 962720 89735 331777 26…
Output: 113649

Example 2:

Input: 1721 534006 598102 257990 79846 736234 613999 900320 419069 845674 348312 817003 466539 243677 325663 450931 89925 42661 546816 55653 820279 326615 13559 10584 145549 533989 977601 756188 686108 840170 496562 492360 2259 539748 588549 43988 763414 726014 1768 778453 918893 229096 931204 993812 836306 923889 589241 487124 95357 644583 410770 478657 580295 995633 679439 899948 406518 427016 621311 229715 855203 625748 597761 614325 764730 292525 600847 419443 709529 828803 826510 874215 466058 256238 892694 584567 925978 706868 99268 747333 459201 805120 197531 848781 506816 421655 67893 702166 20845 38947 617456 689027 404087 855042 798985 263445 241674 925138 822555 158378 550888 368364 577888 853504 408820 912569 113107 268944 274989 158120 923793 73215 669440 703212 933766 567074 558591 …
Output: 753533

Example 3:

Input: 342 330 328 142 316 284 325 218 161 277 7 214 164 274 219 242 89 303 221 288 160 190 202 146 155 313 259 318 329 299 302 262 297 257 255 188 95 23 169 32 110 41 168 309 332 210 121 66 331 223 158 68 165 225 5 244 33 273 275 206 108 22 17 254 236 264 107 147 61 300 200 172 150 59 40 269 81 3 131 186 69 97 25 16 278 20 286 45 141 24 51 1 31 248 198 136 243 28 143 241 26 133 246 14 102 226 145 36 215 92 109 237 183 79 148 311 105 37 139 192 281 93 71 220 99 116 8 113 6 216 75 149 30 29 72 289 213 115 263 212 56 341 337 156 279 209 230 207 251 2 247 114 27 39 339 44 129 179 258 238 52 88 100 193 171 324 140 128 91 320 292 285 55 178 144 211 235 120 0 323 321 252 295 132 234 239 296 10 11 76 203 101 117 283 335 166 271 326 47 70 18 46 267 87 260 127 130 195 162 90 245 173 205 224 240 153 231 17…
Output: 29559

Constraints:

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

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