CT43611

The Brass ledgers of Dante

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the gristmill of Rye Hollow, Dante the measurer keeps careful count of the ledgers. reconcile two mismatched ledgers, every figure matters. 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 <= 1983; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 1336 -80153 905857 792302 510036 438416 859874 -757403 173428 175459 -607124 -792026 581373 745305 102678 40367 751562 -833411 -4837 820317 -101049 825816 245371 -491972 532608 -413248 -70588 327011 -422400 -705934 789642 564940 -225896 421194 311186 661486 770515 96012 30754 421579 537282 -647983 -858808 -372239 341876 -601977 -562420 -442557 790822 -204920 293892 591186 -781501 150288 -923476 -456331 -589879 -321963 946404 434724 -699065 630064 -368974 -186502 -304130 -928350 821606 -842887 734439 602127 -25106 -186982 565705 795870 458167 351035 -842656 765640 -443935 -278584 -386096 842488 -822912 -305457 -535251 -595972 -232917 582785 363304 -500309 -490832 -888814 -7509 999001 103651 -478569 -400952 640367 -154932 -569562 -914457 240564 -791915 955818 634025 -387402 40296 138642 -925…
Output: 450090

Example 2:

Input: 226 222 212 1 211 137 142 35 138 160 158 150 140 83 67 199 93 167 213 108 154 119 194 172 149 71 173 201 11 221 24 9 151 139 90 202 141 134 128 169 219 114 66 161 177 171 88 86 82 170 42 107 132 162 10 101 30 215 186 20 59 62 12 164 116 153 130 178 73 224 72 180 189 183 127 182 7 113 64 78 50 190 218 115 103 14 225 157 49 61 97 163 209 58 210 54 203 155 145 165 159 53 55 52 152 65 3 131 148 4 109 8 77 70 206 146 129 63 75 105 197 214 188 79 60 99 6 85 43 117 46 216 110 47 204 147 36 69 91 25 26 125 22 175 89 223 205 27 21 48 179 192 102 200 217 118 143 95 16 112 44 176 68 122 56 100 31 207 32 144 111 193 196 168 81 174 181 191 40 13 96 87 187 15 104 166 18 220 106 57 195 37 45 184 121 133 76 98 39 120 29 124 126 28 74 94 51 80 198 17 92 156 185 23 5 135 41 0 123 33 84 136 38 208 34 19 2
Output: 14549

Example 3:

Input: 969 881324 -789663 -340262 637209 987837 -410909 938049 -405962 55627 790521 404428 -858500 880132 -711831 699574 510427 -679379 -149627 755284 723778 -879543 -415151 861068 689823 -59064 386978 -184118 -168516 398834 41848 -984152 -364557 49628 -899286 -683790 986838 951109 125688 -245127 563271 -408228 576218 637989 -142767 138940 637418 187132 212662 698404 873969 -784187 -514005 687283 259405 -344436 5616 -593901 29125 -704804 -503766 695091 -479406 426958 -402698 434704 -10947 -665790 210320 -496269 705795 -818033 -289453 -239241 -559750 -737427 202050 907258 966873 -509025 15674 185931 670717 597151 795436 261270 -182142 -503992 795150 -204001 719426 21744 582237 -61560 723324 712519 -516348 -634988 573257 467794 -935677 628956 294168 -255459 22752 343421 -911127 394874 -74817 -56252…
Output: 242168

Constraints:

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

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