CT46292

The Obsidian Disorder Count

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the seal rocks of Barking Cove, someone must forecast next month's demand. This year the task falls to Miller, armed only with the weights register. 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 <= 3103; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 2643 -305972 -992099 39793 -684659 -700427 234157 -508832 716034 242352 -641551 -401331 -130144 -524233 411105 -894440 220638 647489 878418 -661030 782578 -269659 210349 -823041 -759840 -611458 -421346 436854 -100359 -878420 228048 257741 -701760 620502 531316 -731656 563956 955163 -965519 941074 764861 104185 -650778 -329071 -641719 -474373 226947 -967039 -846405 -528244 -126471 -725203 629296 273050 264605 986151 289034 734957 -735942 -149094 -384713 -718805 -908412 -671665 647321 86303 -771411 694274 -912755 180805 594155 -658959 642451 -833690 -901580 833272 948424 -788890 -840718 -304135 756473 22909 542194 214627 -417244 -493208 -979593 93251 -225984 33235 -645726 -146378 839428 466830 -525546 -937670 30878 -399442 426416 -189999 -837285 904969 51982 143830 -20404 47889 418633 -15479…
Output: 1736765

Example 2:

Input: 523 140 316 57 511 101 451 40 190 374 23 110 154 496 215 277 144 512 176 331 15 181 360 254 164 44 414 191 367 42 357 30 35 398 311 324 241 96 463 156 180 221 351 504 340 358 343 118 364 341 348 260 162 196 269 307 36 107 193 250 255 279 264 375 253 440 397 370 468 19 119 330 437 89 461 436 11 75 174 104 318 34 476 368 394 43 495 306 39 322 302 390 200 466 195 132 185 212 379 278 136 453 167 187 182 485 197 131 432 230 207 480 520 106 263 487 60 469 431 111 470 251 2 484 294 32 296 91 92 235 506 400 359 245 246 298 428 366 429 284 388 108 56 514 52 61 208 377 491 344 125 336 102 435 90 405 16 78 124 47 335 500 291 68 10 347 342 145 455 323 411 243 147 507 498 454 417 292 410 420 28 439 443 482 150 462 406 395 380 105 393 386 247 112 134 447 409 474 98 205 115 258 283 76 399 510 471 309 274…
Output: 69948

Example 3:

Input: 1621 388333 945568 601145 900035 6708 156141 942716 69817 857866 -634417 438880 -74311 -765151 -500901 -38012 -520532 650703 316125 -864028 979292 197115 400591 364618 848131 -224248 275320 -867343 773292 752913 -348280 925588 489297 -252275 -448686 -974237 -418416 778770 477802 -419397 774553 -357432 568968 -118878 -509146 -510223 -652967 -457056 120385 -98277 -997096 -94415 421900 833597 273772 -974141 348707 -309749 826169 -604662 -951310 621474 984279 391471 209904 -776579 777065 581505 -26881 -926439 167084 537592 -269312 -883007 -253495 -664894 -889684 470009 -332354 -592674 -885703 -341974 320143 544166 -984384 449381 452348 205327 -461738 935003 144259 617905 -474046 384991 -210918 475809 -248773 -730063 -388626 869646 -917604 -695452 621912 -427127 420626 53539 -33422 243932 -8413…
Output: 630895

Constraints:

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

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