CT47983

Milo's Sable Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Milo found an old ledger of weights in the ferry office attic at the tulip beds of Bloomhaven. The margin notes pose a precise question. 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 <= 1258; 0 <= a[i],x <= 1000000.

Example 1:

Input: 31 297056 818173 898435 697330 843549 660928 494301 486550 181596 427780 718853 417468 622638 300773 956993 272333 197836 912414 823691 524849 894925 26333 819541 421836 303188 370969 490243 177263 670763 985442 292012
Output: 263

Example 2:

Input: 723 753399 262066 82737 893129 961896 833967 658071 523407 182589 61585 637264 640310 683724 707564 385106 901251 887244 475544 339370 977484 583139 734021 938870 226613 991239 948017 360649 682642 421404 445095 195983 227534 359424 433622 893454 560128 668752 828998 709099 814686 648736 6207 357184 474503 440592 178163 698483 650704 975511 332346 423892 203040 263759 76158 717837 728063 398919 603819 160062 711029 88852 544385 621445 433888 37194 958703 1126 488622 990621 534985 503873 292672 219366 390693 73727 282955 790105 943060 346543 25854 194999 908378 109500 278312 12864 687098 500887 433821 279394 676081 973840 757365 443912 420747 838727 588545 378713 91535 237810 46223 642437 360170 511495 962325 792009 138550 278450 387679 361422 903184 887664 503415 780909 520815 111539 42080…
Output: 132429

Example 3:

Input: 171 315372 660835 723945 732528 923325 501481 845267 654500 725493 975457 519244 960700 728359 410483 699502 618759 484239 745226 132289 23698 382123 485214 344657 251762 983247 254430 592771 199683 369171 29707 297385 982282 908096 605848 187471 832583 505692 553296 419630 510469 278372 961446 958113 711752 314123 207954 283322 629770 11543 921367 774293 171667 523459 152400 64955 468528 989201 634114 496831 464296 253680 370546 430329 635596 284380 654150 222281 160166 658564 560667 399464 236046 807927 856982 287480 211749 26736 835564 319411 946231 964051 715748 145540 362266 379206 153684 468136 577260 566195 405392 506556 474492 50358 227969 376655 271389 530658 719677 389696 822918 111356 886716 212875 254659 115893 222224 528000 90338 634905 756918 926287 201555 221063 370296 28203…
Output: 7735

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Milo's Sable Ledger - MEDIUM Coding Problem | CodeTikki