CT59236

The Disorder Count of Alabast

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Minstrel inherited the granary at the ivory gates of Alabast along with its curious bookkeeping system for vials. Time to make sense of it. 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 <= 1552; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 1432 -22592 -93154 921631 -583496 105385 -855979 98408 -554319 -922218 -561642 364647 407797 -831237 716686 898405 -454825 -503006 735459 -830186 939581 -143351 96430 -257265 761479 764107 723802 -762339 455537 -89962 -870401 957574 231910 354124 -945805 887563 179067 -214384 17677 -87567 -268683 686457 -828262 -238325 742691 337072 -485167 -107572 -621311 -396586 -535040 -290189 -765128 -325115 -212816 -62753 615983 531599 19311 -527508 -864688 -723282 962323 311463 -281654 -563257 -91300 828405 -544385 -31072 -529987 959075 626648 730882 103335 -264639 629038 -694062 131206 473151 -242392 305938 624962 683532 139599 224701 -552125 -294262 1257 375110 529201 775367 -288655 716452 97194 -555713 58511 -22007 329827 676845 -189933 188644 -692292 -21096 324829 575358 -558771 -666771 264507 21…
Output: 501572

Example 2:

Input: 737 709 234 492 611 683 502 246 521 322 86 425 155 553 225 503 184 405 638 135 320 413 180 447 723 210 291 702 646 52 668 95 594 310 500 314 625 120 10 489 630 147 563 444 290 669 536 369 262 188 518 486 51 379 325 114 559 548 73 264 328 335 373 332 540 599 506 11 324 453 717 458 347 311 334 223 24 558 248 564 297 113 485 493 645 525 209 187 634 68 205 566 602 102 408 182 585 203 66 269 412 609 450 211 426 153 178 616 169 672 375 91 27 719 539 700 721 473 390 46 131 467 501 253 688 344 149 629 318 495 229 520 532 526 15 707 454 724 565 481 655 696 469 648 388 348 704 624 296 336 431 542 212 273 596 145 96 697 400 392 366 667 177 471 477 434 304 349 168 395 309 538 507 227 29 115 282 422 443 14 360 294 665 126 362 652 206 588 80 574 127 449 387 179 4 576 165 720 315 13 727 692 394 605 463 4…
Output: 138566

Example 3:

Input: 682 87220 227082 -859818 -817855 82165 -53080 685198 409696 -936954 50910 -149757 -469524 -370971 240981 -538302 212608 533137 -927728 -69111 -240282 -311063 -117210 -561047 -2590 977313 18612 490485 920510 -295657 -553858 766591 -586494 858464 -968902 -282867 320602 -483143 999366 907445 729477 32130 -666352 -402181 -334186 485888 242562 -779569 -292954 826457 -261979 759427 134696 804518 163869 49640 872165 57410 -642195 954347 -284281 -471218 -923604 -606561 -460672 588564 -607251 -655040 -527352 163129 41182 -591024 -608182 -262330 -138763 -176198 -13405 65235 920638 -591989 -586861 -833388 578328 656900 396192 498409 -45511 -113568 -782736 -331085 976738 -954025 -694364 -217345 377293 62146 -604095 -912668 731661 715578 -338476 -460922 -640274 56753 206005 240816 846649 612823 27825 -…
Output: 117491

Constraints:

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

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