CT62533

The Disorder Count at Cascade Vale

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Wynne runs the lighthouse at the ribbon falls of Cascade Vale. Today the books show a list of crates, and the numbers must be worked out before sundown. 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 <= 1884; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 1233 409773729 136484515 831649846 142261889 581737965 266260622 230143328 740105353 188158717 44666307 467059938 733333356 518595292 782014617 342635759 345032826 838149966 665838635 922164322 954018149 106556605 52883757 734086951 634162125 969919742 386884032 152477017 229466381 136984360 959884956 640317810 541612798 880885312 332441785 430506945 479522027 29389386 224930185 923596238 291367970 149353531 562050231 458209028 369236047 500186207 957692924 963387655 528228649 766216850 430212559 395211692 489257724 868108650 748277289 613008367 285449696 348393740 796527686 277216739 578805376 780634846 118528493 48470309 979350708 102273333 125669072 990961465 461116528 467977014 828767502 462721616 724622956 467116439 426089261 234858764 579349917 635992196 472350089 395428335 865814776…
Output: 381549

Example 2:

Input: 1075 503214852 64117948 945860659 518184439 696287741 756682893 456097877 989799100 270356489 866783970 273252298 931691790 832865616 145455325 531188072 695378306 717228582 425833839 395802049 575734958 746581111 508328741 866770967 50672966 816624986 386268683 420445685 765395932 742248447 238943923 762645176 841703130 427980644 132025797 716363781 457407654 234542037 406663138 276469007 39409090 117332491 151862051 428747373 730420290 235248912 279243722 758065823 416295721 933593564 814996320 157804722 151756826 799876381 157238708 248979697 997205512 162323065 616007978 535134413 984931479 417880223 268741525 779950518 278598379 913131092 688945367 662291203 316764186 501825732 360327068 445836631 3503055 910505492 92296551 725420295 738261973 623877955 547966856 23309241 564426314 86…
Output: 282201

Example 3:

Input: 389 186 168 63 279 242 30 271 88 43 330 285 198 134 194 12 153 2 311 349 150 146 46 372 234 202 215 339 218 356 107 366 47 387 238 182 257 156 262 173 129 27 258 274 93 45 200 385 350 307 166 87 286 86 203 253 142 192 183 29 322 327 275 9 276 314 269 133 131 277 32 177 170 312 164 206 355 123 62 102 334 189 331 36 319 229 80 39 77 199 152 167 268 3 292 263 110 103 4 380 256 209 197 121 148 260 124 315 248 37 231 165 16 228 53 303 171 232 82 211 90 161 17 169 6 214 369 34 23 376 26 101 299 84 115 282 72 127 240 287 217 10 244 284 73 266 235 7 22 233 67 138 33 25 14 70 40 140 298 74 212 346 246 230 172 304 300 204 190 58 49 113 18 360 357 48 245 0 309 213 259 267 272 44 147 122 328 94 341 125 295 137 151 185 270 306 373 180 99 135 227 13 139 35 181 31 332 54 50 251 302 69 178 162 66 83 78 64…
Output: 34937

Constraints:

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

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