CT43759

Last registers of Wren

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the anvil district of Hammerfall opens only for a perfect tally of registers. Wren means to find out. 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 <= 2244; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 1517 41029070 403887093 226547632 181447648 69180823 872752050 684417758 763850875 303281299 346761868 425148236 917865947 160703789 667974791 335674734 930103703 893194452 597094064 122377759 864518901 297842659 432050358 195366375 300646280 782034877 81531140 180962968 162926273 220243807 74883421 429154068 29932872 467117935 448562845 769061576 215442034 319641275 184753955 497655359 804743582 749930732 285780988 221471353 134797077 301625664 193801307 318340288 588814277 842159874 863693140 392241105 287600778 391326503 774074886 689547491 810548877 756236919 92551410 701265890 872769867 68332285 131383927 551386032 76646166 11893349 876082337 589534118 44315157 876559719 75186338 759893722 170785106 869007805 915707111 108326249 345113831 292408925 700627803 618385245 402221034 893089…
Output: 558958

Example 2:

Input: 1676 258660329 333844833 179188515 200080071 116893593 477661869 157694168 274630578 439146888 980352159 474200567 264991425 337587235 108773430 933276503 131660350 663960399 717414331 618442316 243667816 390252 173563280 424912278 484284600 391359759 408630605 337541949 57843134 693088592 291360212 908041946 625206447 58684427 837597740 522869576 758560895 630952550 941914170 940722588 603476691 837759132 689873977 505678664 818653270 672511198 907708169 868771020 262256096 104206575 665425202 204361978 275275519 723602257 600380144 973492427 294094312 310167062 85794902 306540361 644478334 943783253 70787204 663836186 936736420 633148419 815349113 522215364 154707826 958258966 680609352 899362283 505394184 458308557 429387765 422583359 671316812 609189480 350425508 649593494 523381677 54…
Output: 700353

Example 3:

Input: 1545 970759561 603365896 8653048 109668592 681984479 117657948 345322975 375722384 246676143 739466370 699365488 479312578 418744602 302193966 387059788 263557373 420641391 434829441 371768892 703816225 869640422 153247035 293500497 129004564 569828319 746152017 19828533 270140921 825308684 838515473 332659620 958004577 370034934 48706850 927546870 589988548 537284266 215818676 656700069 356077139 971792670 996810771 816151057 976938063 461022600 442995708 516011143 71324425 231836939 466358302 582601506 965786983 393438342 931647712 729788650 937188791 223611520 329513118 956457523 122153258 843275370 213417998 18037320 206401723 806177484 838364274 919690136 681636292 979365478 611236449 713729175 544234192 801393871 964938661 97124543 774828568 923925057 104056186 60930823 651865721 844…
Output: 593373

Constraints:

1 <= n <= 2244; 0 <= a[i],x <= 1000000000.

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