CT42631

Ulmar and the Dusky shelves

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Ulmar found an old ledger of shelves in the loom house attic at the gull cliffs of Screech Point. 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 <= 1262; 0 <= a[i],x <= 1000000.

Example 1:

Input: 722 304880 333329 232944 877707 228201 748660 740446 262399 546608 549243 585890 948585 717632 164145 306994 533227 158801 445484 964175 70981 486138 616838 584191 665413 876339 398463 178689 809295 379179 316402 1771 198656 542705 98569 200798 655776 781810 190708 111122 147681 561114 578485 240829 382643 387809 612062 524390 253655 568662 514915 919961 364917 343355 203728 251378 325632 298845 390829 841822 404796 369313 927363 472070 693652 970258 675422 588953 610963 753731 366634 227933 882439 315821 574071 113638 952384 26688 451597 747037 812014 458198 116579 535021 549341 503222 629380 311704 381408 618323 494185 130328 323008 430296 209792 32409 794508 886868 599657 455829 754296 510432 234504 299507 952131 451054 704129 692581 845555 884527 885397 494310 73201 917859 747088 98368…
Output: 128583

Example 2:

Input: 1068 794 621 181 534 889 383 747 810 1058 351 999 235 424 679 520 814 690 340 176 390 125 1024 148 641 916 485 552 648 215 417 705 474 699 901 786 981 199 667 1027 255 737 811 143 186 405 879 337 432 926 655 61 443 911 643 642 686 85 963 132 192 668 67 341 378 262 358 1033 517 158 208 218 897 730 595 636 525 153 994 701 727 623 81 154 149 969 247 13 185 1016 631 972 718 232 147 639 671 296 652 223 484 442 467 113 970 977 469 578 756 334 898 290 797 938 319 661 301 409 554 65 980 847 3 308 461 284 453 368 445 538 87 833 1063 931 542 529 873 471 834 1048 55 887 291 853 851 918 765 550 566 129 180 859 344 672 802 219 476 584 862 277 660 324 971 263 907 21 658 141 677 594 1051 908 935 6 698 28 367 753 822 647 9 1008 516 22 245 896 773 275 103 56 415 57 150 504 82 597 99 355 846 955 343 666 102…
Output: 293619

Example 3:

Input: 835 711 569 535 689 686 765 434 120 32 565 66 448 814 165 305 5 298 541 272 204 276 367 555 446 328 723 352 205 281 67 101 720 654 110 234 578 518 267 89 72 480 233 429 176 739 650 119 594 391 504 545 28 712 596 494 202 501 452 807 264 693 396 250 634 380 131 660 602 319 768 159 441 297 378 399 559 309 586 215 57 574 793 406 519 237 523 815 99 467 54 570 582 667 632 327 801 558 827 130 779 506 330 293 49 714 731 181 629 824 92 354 122 315 339 231 198 734 18 247 199 738 341 320 469 95 207 211 34 722 144 622 729 368 589 707 47 525 671 473 435 664 118 425 561 608 620 698 694 495 194 777 142 154 164 758 318 631 409 748 37 790 213 336 376 597 191 774 105 163 539 524 193 307 261 419 543 141 433 195 606 337 696 274 488 791 260 103 466 508 44 621 456 800 279 783 745 595 415 756 773 447 772 278 189…
Output: 176269

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Ulmar and the Dusky shelves - MEDIUM Coding Problem | CodeTikki