CT39161

The Tranquil Basin Disorder Count

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the lotus ponds of Tranquil Basin, someone must forecast next month's demand. This year the task falls to Nina, armed only with the shelves register. 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 <= 2666; 0 <= a[i],x <= 1000000.

Example 1:

Input: 814 235593 691702 483507 995819 346412 233183 253725 587487 25715 470885 136483 969766 317683 54115 837824 751816 179358 714817 262307 102367 296317 755186 667789 933981 505611 54932 48912 868489 336787 49233 114687 391545 817149 183497 604234 172900 469715 611035 564143 938575 286156 816537 51943 525417 360827 792020 765588 513314 562615 543401 57064 915909 52469 831235 331774 42599 363561 996194 953576 690556 847824 75191 719428 833614 816202 471420 774492 785189 21669 615391 496617 55625 109068 77893 342221 923871 511321 959595 403941 238124 224641 547637 855507 981218 249731 719128 502647 428650 164588 890240 956907 132840 252602 706503 620803 388439 29634 769625 655609 743714 292841 387259 466996 771951 583797 621350 744253 415916 908287 457087 904128 738026 25452 179577 879847 294661…
Output: 163089

Example 2:

Input: 1788 242037 112594 542001 87446 606417 267747 491432 118504 795831 607696 167912 709021 344503 51856 405229 494749 317529 634711 359301 554646 303788 157521 267965 612220 925605 124881 62811 87968 19260 477988 35578 487162 867199 981368 962257 553693 412983 22285 631111 592496 221669 318293 921594 202423 937707 961813 806971 653280 207721 211967 663840 717847 574020 13615 369722 305177 846011 71701 624496 701698 770173 150238 373304 652231 750583 650519 277372 350079 276861 832386 510208 288649 676280 349894 382773 295861 790898 250286 216915 675358 518299 981733 640279 839108 509557 593060 189211 995104 761982 241662 644468 672773 843297 32707 277661 653557 909381 561279 711952 714802 219565 502273 17619 915633 575622 700906 266316 427188 728940 240804 861411 838741 457201 989974 547834 7…
Output: 776371

Example 3:

Input: 1355 905099 614813 452460 537473 87737 323854 867913 275706 713783 292932 212368 293676 537252 477276 777356 363898 285218 315036 828520 994734 461837 886376 645960 797594 58670 154784 461283 311518 209508 174749 355231 488244 464076 653245 160422 666773 517524 567700 278630 211338 571944 74819 888783 706562 306314 853594 37595 783821 134691 593675 666442 655806 79791 681600 266753 155978 175424 723935 92795 433833 369494 237443 813409 572312 352981 150851 819057 207774 977696 738493 497176 345644 797041 728369 978513 871949 448794 954971 543061 706397 770882 304282 679718 127777 968655 678544 271867 727016 95436 527718 24001 57000 972408 574862 445066 559246 395661 757057 624482 486061 143296 316294 838208 617824 296788 972997 963732 173670 79818 901067 956938 87660 694837 956929 735760 3…
Output: 440561

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Tranquil Basin Disorder Count - MEDIUM Coding Problem | CodeTikki