CT44685

The Disorder Count of the Jasper vials

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the salmon ladder of Rushing Falls, Silas the valuer keeps careful count of the vials. plan the beacon maintenance rota, every figure matters. 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 <= 1468; 0 <= a[i],x <= 1000000.

Example 1:

Input: 995 274887 113855 234015 435939 811608 969383 843176 658475 831374 169949 667551 55497 492799 901353 24733 736381 356267 394039 897649 686810 732321 920939 198169 660851 514269 44800 154419 450504 47014 630139 642830 890926 783797 799254 794365 37863 196452 895860 405004 790626 359415 990247 38651 482555 802477 144380 709112 521741 686742 537863 464478 703462 699559 884157 676041 403661 88165 533157 270819 799593 836790 241151 982385 457638 211321 688829 50063 521615 907230 118171 200208 754161 294109 803629 984589 869955 61885 179510 569915 238829 959881 908203 214408 563308 602042 915564 839140 500609 689412 614615 531714 300302 365594 637453 212721 536899 814041 401872 282775 313735 242146 367170 11467 37605 558570 925011 551406 543642 610851 187827 30328 69161 939782 865603 439299 3368…
Output: 254219

Example 2:

Input: 731 32063 118802 124684 599704 213599 693517 286034 252344 806416 648177 707921 508395 866213 763340 515890 429137 167292 355951 25966 232888 96941 246328 667827 757168 171054 334596 869639 651937 429686 714504 579205 201375 503537 444640 152377 676318 582404 608814 475187 34414 47684 189523 49073 719840 261949 464791 112117 491648 517070 739924 269873 189311 51897 753152 522251 23601 749891 739785 98202 62534 324721 245563 982636 48375 980093 705117 128624 1953 81733 845372 5420 806228 638795 324459 181042 873348 670227 812803 271388 683539 298721 794387 981122 557791 437989 458422 380167 296669 622406 431033 643799 543809 225957 265652 427670 623431 451539 560820 867570 838718 911923 404467 404796 116175 638999 635665 703575 394397 94927 24605 942760 782918 261671 394920 392656 296681 27…
Output: 128892

Example 3:

Input: 382 641508 859695 335042 428673 198799 688876 464758 364611 685681 386454 110049 146198 367352 846185 981933 377529 261259 340101 55970 28877 884974 755018 77883 458340 358384 763238 768930 925878 807440 666355 513641 760698 621857 570261 467422 884900 159799 144329 665445 640279 102992 351439 330274 818843 446807 600928 216424 921561 192350 868573 436368 545205 815018 661515 115168 175931 27179 289881 145942 801580 226245 67555 1531 585000 102988 719648 31016 854159 585280 772664 716388 767255 299918 843048 392178 914555 43593 321079 967461 517790 844906 525234 111953 764822 388470 538332 329357 231632 291759 245435 802389 21744 664381 140572 445039 485201 490476 668286 694976 214787 832432 663218 97168 466943 701636 758812 561579 988902 502022 87705 448701 800031 48977 18404 235356 36749…
Output: 35700

Constraints:

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

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