CT51095

The Beryl Disorder Count

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the lantern district of Glowfen. Kian spreads the vials records across the table and picks up a sharp pencil. 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 <= 3180; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 497 -149811 243150 993791 -877806 688071 224020 533973 -10555 611503 -426636 -140926 -782465 -397988 619944 -652804 -75858 -473425 337585 -603507 745581 83684 417881 201461 881958 543855 -310379 -297212 -275869 -398253 -992099 -669551 533154 620264 263946 -920762 -404132 779686 -710347 -202948 -904439 516338 132074 -825110 606664 -324801 -667624 397319 748829 28247 286704 -414718 -654371 -727992 -607973 104773 226835 226767 974439 -917835 809906 866300 283774 9795 -575238 494995 -427741 -879550 73229 326179 -548080 263879 758224 414215 489647 655730 301169 999284 104405 867717 -505121 -638557 -243319 -640727 -239282 -139437 221552 -694800 876224 -897644 478163 512004 -123957 -335795 782588 -794767 901394 -337683 229613 593354 924873 893437 -340445 -202851 -499828 235566 455424 645319 69185…
Output: 62740

Example 2:

Input: 2521 -223359 92879 249882 608855 165883 169205 916385 10093 213882 193680 467653 99677 486220 961827 136519 -824528 -975735 -787377 -669264 -441207 837342 -548952 410188 390071 -574313 579802 -120929 -505859 788882 -346637 306635 342387 205270 18705 -512719 -687211 -39517 -577882 542592 -556694 -293376 -79400 -196706 423786 705215 -208355 710054 -594299 -566293 -868664 -16200 -468010 -212241 -417212 -893004 -164860 -572396 -95602 -938128 -536505 -465828 736353 -947982 236122 -801495 -967896 -565837 -824091 -628813 -973911 558195 871072 504087 7991 -634915 513188 -744277 -903670 253320 271326 367247 -473974 -599411 -488506 392665 -593358 -573105 92599 -76973 -305166 216803 -280338 622014 462048 827774 74135 -655586 668206 114641 171692 -365919 122868 -453475 963288 429684 558942 865588 -115…
Output: 1572694

Example 3:

Input: 588 536957 -383062 568336 867815 -700908 80843 517248 -513355 -524384 -623535 132096 700210 31361 716470 723423 670046 -308924 524392 -768747 -926039 399548 294713 884865 -112975 -584843 487480 762263 942014 997916 561241 -349610 714219 847995 418707 -838722 -242145 -89428 -337548 310187 -750109 833871 -116102 635979 884677 170259 -430414 -532115 -597095 -637505 354609 365282 -12016 109077 -425400 -107973 542846 -822123 820982 -614832 658076 334592 443030 829062 126046 -886649 -220765 52383 -761220 -907572 943802 -29313 607621 344845 578341 391774 -807649 -583832 -81208 458084 -991791 729704 593216 502412 -711283 -378517 183122 -553270 294068 -496362 -64714 -408854 457113 920671 947499 831454 -356877 -540770 839507 -117327 -903853 954728 762605 -339966 -399528 -654726 458029 906291 384685 …
Output: 89229

Constraints:

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

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