CT36792

The Brass ledgers of Baron

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The council of the mushroom groves of Fungaldeep pays by the answer, and Baron intends to earn it. First: the full register of ledgers. 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 <= 1108; -1000000 <= a[i],x <= 1000000.

Example 1:

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

Example 2:

Input: 391 342 208 390 195 98 125 211 13 65 292 74 140 56 354 162 315 112 276 27 48 146 17 145 105 159 341 58 215 194 367 344 61 176 155 92 375 107 114 361 312 0 336 347 280 170 62 376 172 190 122 282 323 53 202 153 352 254 319 185 294 30 138 219 76 120 291 54 84 353 365 32 115 147 247 382 154 21 126 328 217 348 75 36 260 330 278 296 379 302 28 285 339 297 229 385 135 63 2 227 337 200 290 322 165 113 52 370 148 334 251 214 314 143 132 111 220 389 279 359 142 130 309 281 222 139 152 277 68 268 230 26 213 203 338 66 183 305 287 204 43 189 81 245 9 388 284 71 356 244 206 136 269 15 51 221 307 157 175 72 383 267 110 173 318 380 321 179 265 22 293 91 35 184 83 166 38 10 329 249 212 301 141 50 271 119 326 201 29 57 19 94 186 70 374 101 187 144 283 131 20 226 387 362 192 298 270 378 18 368 85 174 349 79…
Output: 39224

Example 3:

Input: 923 893 548 33 815 269 828 530 229 370 170 615 888 418 24 65 669 760 684 273 778 569 445 553 262 276 195 812 667 172 291 842 252 717 752 153 913 817 679 583 535 672 640 772 98 378 714 786 506 699 589 142 623 850 855 272 517 171 481 560 144 641 396 595 259 218 459 482 579 174 63 194 76 226 426 391 122 233 376 373 203 636 698 127 665 14 705 109 901 854 316 876 424 192 511 761 334 674 577 840 368 527 804 632 789 908 364 907 86 387 324 834 128 327 813 37 874 728 34 120 56 793 474 662 591 191 345 702 664 48 904 830 827 658 247 486 277 279 490 729 900 392 748 768 599 140 75 110 718 853 606 263 107 587 671 257 202 769 609 892 639 131 293 355 28 791 594 921 502 650 777 675 647 510 268 479 770 82 22 61 442 132 254 55 617 249 902 5 156 659 910 783 773 758 457 755 315 487 283 782 425 217 578 448 610 …
Output: 224128

Constraints:

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

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