CT35407

The Disorder Count of the Granite crates

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the fen lights of Will-o-Wisp close for winter, Elsa must finish the crates ledger - one figure at a time. 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 <= 3441; -1000000 <= a[i],x <= 1000000000.

Example 1:

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

Example 2:

Input: 494 52 290 128 113 396 231 474 188 26 43 114 17 435 12 126 415 426 400 319 101 197 1 29 35 324 70 238 239 450 7 208 490 176 207 330 352 300 393 389 476 200 370 268 42 0 366 220 347 403 486 480 418 73 183 446 56 466 127 41 301 2 398 179 98 159 9 296 417 194 10 460 372 422 439 212 250 93 402 217 60 448 258 184 401 488 246 222 198 340 269 388 90 115 85 463 253 67 413 181 187 225 391 458 346 196 237 120 166 174 112 106 447 397 234 33 338 64 191 419 144 479 135 449 357 18 145 368 399 219 76 69 226 99 140 282 103 223 57 54 11 272 286 478 257 241 267 425 314 318 305 32 263 170 116 46 484 21 110 189 433 143 467 235 205 477 141 79 456 47 80 146 392 451 464 195 291 259 86 423 165 424 163 118 310 100 31 332 109 37 278 394 289 72 297 327 341 411 485 379 390 13 63 68 293 378 150 453 111 190 158 351 339…
Output: 59730

Example 3:

Input: 3209 318267234 321343956 589844130 99399497 843780325 60952631 429550836 370808815 253504096 327056037 991319176 554354102 270713373 34114383 105190555 595254911 354739549 495668290 455932566 766483285 342152354 140362472 777781864 747136817 532213330 148823940 883240056 190292499 141876038 562639196 528233250 698642985 918792243 378343334 79663553 856900674 807484041 768762764 514344507 754270815 648746213 755913538 523867145 701673076 574547766 266182028 261171992 556453382 407887329 230116352 547572348 523735213 945123658 466006504 37194001 505179128 553459120 464780009 23366578 56693640 393664553 61496757 913301055 856293350 568650076 912761996 890794864 149196309 85310374 47156627 973961773 227742823 460875172 289331792 722162341 314399032 20709687 201923336 246057922 103472786 649176…
Output: 2607298

Constraints:

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

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