CT63549

Wren's Disorder Count Ledger

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Caravans arrive at the gull cliffs of Screech Point with crates of ledgers, and Wren the chronicler must account for every last one. 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 <= 1589; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 329 371543579 595874410 304947094 524809441 327603157 511216205 472612565 285068625 840942664 505811927 785302949 899736742 816284663 127095436 819731316 720109530 705250521 216719323 917171759 158320974 453073335 687647917 12566060 271183015 479762729 119675306 420370952 186426600 176355949 432381545 579075746 147526264 189498687 200480909 671269127 758865958 689273433 284830388 851335638 804405853 554524365 594428756 614306282 584037660 31410696 423729630 337917521 494393609 611943726 127632506 80322048 96870734 118578480 884471794 95457062 508498064 561613815 727627175 43219197 401342603 596960337 131573996 474047779 896992288 388568892 371252051 172528762 399717371 564155787 137139790 289096813 621107178 288639013 235772735 922775568 991216435 839651778 251968870 954840751 446340841 29…
Output: 25512

Example 2:

Input: 917 695 479 628 911 34 463 302 662 457 520 734 727 608 677 288 649 442 517 481 786 339 22 242 676 637 239 816 402 551 508 601 171 674 503 785 115 584 630 397 781 421 573 201 222 185 389 148 182 859 747 246 351 912 880 615 538 690 524 104 17 39 825 300 609 163 774 512 134 200 836 295 424 372 149 498 208 75 441 658 23 325 530 692 710 800 844 788 673 646 484 282 590 839 11 529 81 369 413 252 231 196 861 730 668 604 834 278 644 446 275 625 260 335 759 259 263 629 321 7 832 386 768 221 376 883 500 719 338 404 890 111 19 184 531 213 636 735 326 820 808 862 84 243 521 887 328 733 461 663 118 106 811 299 210 217 108 694 8 567 539 169 488 113 126 165 665 718 471 600 602 660 478 593 343 595 385 453 578 760 18 835 793 721 280 265 214 254 418 61 176 669 796 698 854 183 664 849 506 435 866 154 235 723 …
Output: 217919

Example 3:

Input: 1238 775462807 755363607 729606122 208715809 606483543 504181202 465994709 696109167 707043074 450289015 254430122 752626362 817689154 308987869 131108775 795956398 417497176 726389365 806929709 540817843 952318747 612648503 185612139 593397877 353011397 694129067 334359788 475571844 470335535 59599128 171597083 653074890 641574147 961485119 24507268 616763191 714339505 32948170 448944518 775146925 835295289 315293769 406700758 343086546 181078710 631832687 493123327 358329119 667986834 937557240 15849181 172762996 868616896 414149129 625995558 184459967 578876233 3574764 645284309 948683057 696382205 426491584 515342981 467555363 296534374 14475219 124647726 436134266 599095057 425706858 744327368 499028425 83424478 879949653 441543838 314075162 227110202 433776884 23967822 640109047 9807…
Output: 375144

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Wren's Disorder Count Ledger - MEDIUM Coding Problem | CodeTikki