CT40238

Sahil's Disorder Count Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Sahil inherited the workshop at the archive halls of Scrollkeep along with its curious bookkeeping system for registers. 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 <= 1095; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 893 567645154 784326268 879843055 187088169 692837612 202022057 744934574 138540006 718812664 521486086 291326672 917691738 503566785 134280139 431067447 715809084 68835516 80673318 348678267 606164913 184728738 321091773 477442599 472776021 711094616 112638113 121825403 229796369 500354515 850117685 792236265 596355748 835859776 849202708 722888965 7525759 388010750 265824990 326102034 59279840 263590554 450286126 697066668 691434059 955465718 758613568 427714269 804629748 184580431 868796334 471956980 42128065 127461536 846211229 930460426 437174835 230696622 955991430 500132829 957537382 115187017 901415329 414762212 108194304 986324492 449503056 437786513 779575354 585997665 624847229 7675178 164468101 86889888 759396405 404488340 815844859 316742699 377920376 637951191 958330677 56173…
Output: 198561

Example 2:

Input: 618 26 406 62 459 559 220 500 101 486 383 255 602 181 473 312 608 178 430 497 522 193 376 484 384 190 520 184 511 593 341 143 141 507 394 333 29 574 50 64 223 492 533 83 409 310 458 613 186 401 265 435 415 407 477 569 214 475 80 126 374 595 370 414 556 72 399 599 550 111 342 322 403 284 174 95 102 61 17 561 445 424 601 92 432 79 335 343 433 444 431 118 339 578 21 443 439 377 30 234 316 136 248 361 13 239 138 275 480 617 564 170 575 242 168 464 303 413 235 566 129 346 467 318 570 529 425 393 142 160 60 592 285 2 41 417 563 396 11 147 375 351 290 448 9 521 90 390 330 25 132 535 59 250 212 387 91 594 582 547 598 6 541 456 603 157 479 260 579 231 327 499 188 93 565 463 282 226 423 135 332 204 355 495 200 612 86 125 323 238 360 573 493 558 161 85 532 306 202 185 278 470 68 302 347 63 122 291 30…
Output: 100600

Example 3:

Input: 949 885384850 558977487 413229635 481411549 615953461 707127574 949243800 103936689 408699704 415273533 509590040 886352230 738156769 729234977 192274364 3313099 283771201 593148326 875553175 37086581 848863934 46903281 280022867 537243723 732359366 415668059 538498574 488479749 963066009 115279817 690912518 736760344 470302294 100807033 624327116 92996485 313783039 271415051 281107270 516966699 630449110 839540631 737754694 568363950 771672207 975029463 612933874 879720538 510032116 246743358 263554152 365211803 669470554 150048192 591021595 20756569 496401305 257389131 212679792 562089601 346783556 214544158 462082211 161783049 665700125 621392673 73466218 558143856 57624314 990345803 992681853 43280686 369151776 887103980 365793256 210590626 559898787 649835982 566006458 381539946 85732…
Output: 218305

Constraints:

1 <= n <= 1095; 0 <= a[i],x <= 1000000000.

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