CT52393

The Ivory Disorder Count

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Clerk inherited the greenhouse at the observatory of Starfall along with its curious bookkeeping system for vials. 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 <= 1681; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 552 889380481 16635630 998796145 992836631 724666450 633775661 135938990 513182571 402909622 483478396 346849535 233230671 813551350 464706020 966422813 582879828 974755632 188142379 351260591 377111721 582780976 552533711 564886344 42984567 331059510 789490808 269694822 160649371 215044821 166467521 987286229 600151486 178687095 408840886 819128625 476383810 333546157 878106051 473332104 298208371 850740081 624293626 641702769 29351537 495602950 185054893 119907658 159976236 469011676 39061107 778889513 800965802 147442654 428755926 215907734 920441623 41413578 76780473 646491349 864263787 256684333 477984930 597454031 764891557 860812932 112463523 541041885 445268585 422323811 462374669 591692333 481625527 586855617 128496681 695653373 998119480 154254260 904053586 712957373 834350115 27…
Output: 74912

Example 2:

Input: 345 120 32 108 56 309 307 271 258 245 21 34 133 280 79 275 92 223 331 173 169 35 305 228 207 306 85 58 0 74 144 179 37 146 224 287 157 255 22 165 7 292 235 109 3 221 41 339 16 112 226 171 214 341 279 324 129 242 52 220 326 102 187 143 28 135 202 150 289 73 71 47 48 153 342 57 97 154 70 103 125 283 107 200 95 333 96 272 253 76 265 325 93 263 31 100 63 198 254 262 140 180 111 60 141 249 304 215 217 231 232 328 166 42 149 285 244 298 91 6 218 1 238 205 130 260 46 36 278 136 8 191 291 44 115 55 119 61 318 239 69 43 332 201 212 122 222 13 167 270 89 196 320 27 261 98 281 113 118 206 178 314 322 126 64 243 53 77 175 317 123 11 101 161 152 23 210 50 312 330 303 335 199 234 313 33 233 84 131 302 78 327 274 19 204 246 192 195 334 156 310 319 229 17 106 39 40 268 338 264 159 83 45 181 68 66 86 59 17…
Output: 29171

Example 3:

Input: 1248 141460410 335098664 55423850 720823982 776367530 663213189 538658208 744321584 299461681 907492961 3592859 390418182 2115659 533692026 856936806 360079677 5892196 168370823 578419210 822244952 116674026 347263937 895708556 672071543 823918680 943757071 751882742 719161374 149841470 976107383 200152816 722199603 806764904 879925961 655014402 980422700 102862989 623609967 277975408 977882937 829368486 786278067 617904401 984432695 922220393 55126055 133470614 768220680 497940635 556870710 846212590 913266173 960625429 171124054 361698848 499279866 916477811 458986076 766799852 156769158 9817445 936742466 578789665 575399562 864366156 356083516 425992008 32621589 951573546 874754399 175307818 900288280 500423085 900818091 65909800 536843324 921952690 672782546 116075672 601883521 2656527…
Output: 396944

Constraints:

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

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