CT46182

The registers at Verdigris

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the copper works of Verdigris opens only for a perfect tally of registers. Ulric 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 <= 1057; 0 <= a[i],x <= 1000000.

Example 1:

Input: 857 777211 852148 772056 978006 785580 448026 962742 967218 475434 524925 682637 599288 758868 409992 129115 843039 786922 611563 56294 873110 748389 329784 353352 251105 496814 768889 552305 413607 196068 1272 902706 710764 690153 958414 777193 950485 737207 881554 777881 54227 376810 388669 838434 118791 61283 844459 38868 195797 997345 784952 413229 42928 299766 100079 335400 156938 802201 502690 610820 355301 211578 600461 51799 858437 976185 611055 513902 796027 727558 351933 997667 110868 355298 409071 751500 373488 321190 901667 535091 789018 731955 812559 368700 293859 726322 748183 509341 773409 107214 987787 64936 178446 481613 644293 91655 654114 242871 690762 90392 488224 933224 562064 353733 208295 426442 741254 44959 753788 606813 995861 578724 551129 871493 707594 222376 341…
Output: 185284

Example 2:

Input: 674 441900 106109 849198 69802 918268 917724 728914 915352 911860 31240 986944 173711 194417 248592 673052 479572 505685 906021 108510 887600 545403 454625 753341 319063 342021 596133 752468 352906 576620 7512 507417 322326 675894 503903 284675 994452 628789 72345 845782 437028 876473 812449 69345 440781 214816 496474 258391 315778 505655 856081 985850 855065 446992 129029 180067 873149 492169 851468 578227 132651 114186 2023 193062 175164 319351 605464 35658 688360 449781 831991 571595 771367 243647 216236 513397 288030 74237 455075 184220 241070 565100 533589 130108 710064 184051 20114 994135 389659 6502 885067 317101 457 543925 147874 929322 974607 258712 290719 630577 130316 9759 927195 64402 386148 720268 62116 112120 565483 532214 123648 304952 65290 215055 230992 339544 419235 55936…
Output: 110848

Example 3:

Input: 65 39 35 0 10 21 6 8 9 40 48 62 56 13 29 36 44 15 27 38 19 49 3 45 51 42 12 18 31 57 43 34 54 52 53 60 28 7 46 16 22 17 55 37 64 58 26 33 32 23 30 25 11 20 61 59 2 50 14 63 4 47 41 24 1 5
Output: 1002

Constraints:

1 <= n <= 1057; 0 <= a[i],x <= 1000000.

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