CT62438

Zane and the Disorder Count

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Morning light hits the old quarter of Brasshaven as Zane unrolls the day's manifest of registers. The tally will decide the next shipment. 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 <= 3157; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 142 910236579 416241060 634657152 239729113 45109084 489135283 345198775 917990832 890468562 521968333 634838162 542843246 537633714 578056829 629546919 325720998 966517103 234182739 347066109 515878817 2592947 569785634 679646936 822185448 832931995 753722647 656716920 926268090 299714296 46103101 250991294 920398303 602043132 352462739 516494962 806535950 83581657 439542053 767571005 757644585 693522864 499360783 352669848 241641154 534397707 302698353 339840892 418090127 556158348 592649247 151113951 597584421 146678683 414948446 502615197 402714507 638148407 81561575 621996159 677407802 662782683 519378188 831513228 720523420 493742168 625607758 321195417 416303475 158076577 552189276 987241311 922499734 295012157 664489667 720272440 802452079 289632745 67707851 924660949 212137440 891…
Output: 5128

Example 2:

Input: 340 433561418 18863290 107368219 147267979 642378562 569388861 595385955 523193028 747684305 309867767 223197909 664372659 874700153 778437229 980611458 773860888 443610755 179809226 802710647 520253543 992307574 235317765 887590491 825739981 4018857 50390987 63556872 21016005 484790079 566193466 93377669 783661961 61820390 862876430 100227451 336965745 272132020 678132989 808797802 370962718 672822204 918871280 809849851 316149685 213057343 765341065 637328888 630308765 2718052 741083918 954007502 111494909 810189671 589672512 798234366 608919622 146303696 555779669 728747258 808251930 505051229 595186332 310460999 814910132 487225246 363836994 794969532 897316775 162010451 491577967 941156762 747724582 162972086 146290804 859366705 390711946 446846726 184998404 188555648 909301800 938138…
Output: 29474

Example 3:

Input: 1880 568339705 279440033 422314976 99949013 763003695 299646026 203265476 659466693 465568376 129906170 717498297 795015440 390373952 930629317 486718543 906767581 912213784 556536140 901788474 291650621 446095385 328434711 270486993 29584097 662515403 352671198 499814013 24921007 666354585 536439116 856153332 14732009 161126263 841536865 230673779 328922716 316244077 112940090 702211003 708713913 413948527 99083695 860860208 82867467 656064751 345232705 459086015 604788535 151419434 240174756 247995163 865836550 675691245 489543676 484815594 463826206 459140775 912555031 717727843 204778103 587506622 970399852 900157702 746352206 728931886 185306583 559526992 636102561 556613887 920645066 710707039 907811374 28364631 775055457 156432042 431432576 75358565 135191706 620884960 118377870 257…
Output: 905128

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Zane and the Disorder Count - MEDIUM Coding Problem | CodeTikki