CT37306

The Solar registers of Ulrica

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Ulrica inherited the observatory at the peat bogs of Mossgrieve along with its curious bookkeeping system for registers. Time to make sense of it. 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 <= 2417; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 1475 -94549 192336 -554224 -726711 534007 723049 246575 77182 727020 -276146 565838 -586651 -739104 650521 -128721 571485 -390757 -823172 368322 463393 478490 -439982 476308 173790 794163 -216150 -701956 322936 -811151 -946644 -224342 976661 -951942 -109602 -856263 968603 -91644 -543592 146127 939425 666562 357060 217752 805219 59141 -148493 764542 513981 -222170 -538034 -460367 -815287 -525776 725625 769852 776898 555751 359995 475572 710729 559880 902790 -25085 465391 -466182 -603165 917978 -606483 917539 -90747 471667 904553 -376132 -588657 520867 341554 429187 -475735 807270 -146029 535457 23205 831459 908897 722026 -769092 -180416 -473549 -635546 -848871 -288300 985758 118676 -312849 -142200 539773 952252 500506 -841362 -355120 432054 -655101 -939682 -528401 986366 -920122 -627971 693…
Output: 546669

Example 2:

Input: 1583 624467 102408 79677 731436 347905 563126 123753 354950 257102 842775 -459194 -154829 -802089 -911297 94798 455395 198445 -42535 556742 112089 799744 460407 -184456 519365 808433 -5996 -851812 -600015 921968 -981793 -469812 -472181 830320 316619 488265 -244305 776703 600864 800126 -46995 -299629 999961 138246 -744892 -316926 863072 -8972 -837358 918177 886251 101809 -822374 396878 -677816 -299829 361771 339028 884291 -315575 438652 625116 -443458 -38531 -360810 281235 -619856 -294923 769575 270889 177375 -990248 474158 142230 185226 -424451 -926510 933192 -346702 -806911 -94488 247930 512712 381281 161302 -642400 -98634 131929 508541 -21822 256066 -80523 868091 -528859 668179 657995 600739 -188541 -194190 317760 836255 469107 410569 416496 -105617 240323 -169119 315896 798885 341578 -1…
Output: 632313

Example 3:

Input: 488 595472 262370 684166 -447458 -787882 398885 -711777 -254386 -695218 -755543 -518265 658918 974136 991851 -837587 -461564 160559 -751014 780083 854381 47933 493448 -974485 -940703 784167 -130401 834738 707019 590865 -622040 -865954 833802 578491 -515049 339500 -157354 232062 615908 730319 -419748 -98242 250159 -267430 -552804 -731352 931412 583322 -365019 -365445 -374742 881396 400844 362517 539825 198542 -990949 -709649 -382077 201141 919542 809392 -699256 -980952 -408221 -147133 999022 -266943 -389917 -213330 -410190 -121998 -77305 -11836 998589 -776424 -983238 16048 -743517 903847 159983 868150 486368 -682342 647569 28407 210040 654906 -931462 210675 87625 732453 -425089 -479019 502793 -160796 -534155 73756 -875231 -934657 -555784 570255 -85511 292394 20591 232612 498338 949022 28781…
Output: 61032

Constraints:

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

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