CT58547

Zane's shelves Disorder Count

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The harbor bell rings at the ink district of Scriptoria; Zane weighs the day's shelves manifests and starts the calculations. 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 <= 2316; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 608 349688047 954674815 495019090 82017952 484837429 574380415 266755441 15800401 955120107 873365349 180727653 868160335 100075863 826161259 876046349 491051384 366260158 523710562 724989895 819039945 621897661 392607646 820958379 797528241 553060402 604104341 628263327 54326165 816741658 858026643 517813453 314347340 347002509 674179550 382194608 849595429 416482774 800396505 915465859 365306156 656658462 643010830 7011100 644710537 346486605 61915652 39059752 98958079 28229285 278168776 172348056 791513653 853652273 588547153 538952526 304574208 498558851 720551359 612422734 910884933 638064050 451027995 744469309 479141612 594228926 929044225 303931040 360187487 566204300 951204139 603455540 723280974 629038117 359759232 72213152 766494819 678203324 902675013 888799883 402149448 995520…
Output: 97074

Example 2:

Input: 1384 393785046 661439911 465503524 797840626 694885594 436322431 776522619 236511416 488481251 951681521 494958060 388399432 761366394 935984541 665181328 282395928 688045630 567665204 629454631 756902822 513080725 90076078 991369829 913147040 137920467 295673465 441851774 79830398 31204227 563089037 507010389 302208444 99236987 199223066 5307174 36852805 14245713 684129783 892467347 471597378 290328625 814883125 29127 637223480 491496487 102818204 964698598 968492555 266258777 723928555 680946922 549731810 403704420 78716411 303624237 922509873 638160236 393813873 743146575 746487871 122124227 829039747 416069039 969470151 422430506 178706075 838554314 350081763 460969710 451992015 381858420 999809248 298030588 566153599 537305124 592721926 678313704 22336077 118939679 5489801 174556343 1…
Output: 484407

Example 3:

Input: 674 695579597 881434404 432985020 387179463 567233059 408792382 331825487 59925937 628969637 219070948 419545093 868851318 592260221 470017741 266088861 918539749 732045889 893903934 424594991 592207267 665890362 249767653 541195911 870544659 288463013 664854559 653222232 101751330 125334185 878490784 249427951 642461459 37236512 143100395 879433357 453442477 400402856 455785451 43772749 994336926 499092683 571405206 948192137 638979283 100258964 710863748 317687681 331999103 658679227 699493365 968369803 150446111 134419087 445432753 923163000 327109978 495768228 904090105 893408366 966017631 615744266 942674237 817916409 900308649 239648326 146237852 464809098 958196348 321466489 948121645 381813884 993705451 383181221 501292888 378538955 908538941 910516363 637601082 794564452 602681800…
Output: 115635

Constraints:

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

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