CT51217

Lata's Indigo Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Lata inherited the observatory at the coral atoll of Pearldeep along with its curious bookkeeping system for weights. 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 <= 3841; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 92 15435 -794203 877786 -889703 -434625 -542718 -800128 -149145 -686067 478677 719766 -620543 -531613 725629 -329566 -953642 -894318 611415 315600 607563 -685744 -807432 -293998 -274261 -354083 500675 634434 566554 -240221 259094 -171437 -349223 -574642 51157 -744166 602330 -11034 546145 -784549 -237679 -872238 746888 18188 -460631 -575249 401804 492213 290442 -994699 -674526 80435 -530779 -489273 -465086 -100147 137621 -677129 871665 682569 762362 -440084 -242788 946959 429704 563922 118014 141322 -936768 -529413 358938 828258 -525846 -396786 -709634 390135 372830 184293 -227882 992936 -29605 -113550 -292052 700305 -261480 363199 -870537 460271 638758 313949 -238884 -642118 791040
Output: 1813

Example 2:

Input: 705 453 517 24 483 581 618 582 183 559 66 674 248 646 148 506 147 273 682 359 632 61 508 681 462 172 437 226 195 461 449 269 399 234 475 56 223 409 325 613 257 553 498 601 10 321 407 287 495 540 40 312 480 425 99 338 302 87 299 55 504 115 524 227 332 520 281 85 423 313 23 131 499 12 111 27 664 543 238 181 561 570 671 687 161 261 690 251 340 585 192 614 562 0 218 688 202 645 413 215 20 397 33 342 415 533 197 380 19 588 650 442 530 604 316 253 228 176 354 698 139 377 184 235 17 394 609 557 214 699 264 692 329 268 263 252 93 629 295 627 678 648 492 220 455 196 68 457 74 77 515 28 256 163 429 549 376 369 348 388 301 542 60 630 489 327 216 637 149 174 231 626 608 491 550 477 600 288 282 136 535 395 371 88 383 165 245 661 320 695 96 445 230 558 701 78 164 548 672 162 501 240 638 596 59 497 402 6…
Output: 126662

Example 3:

Input: 250 -993534 555966 -329795 80949 96463 -985810 360042 -747038 -77821 427839 -314178 725592 110779 963676 -641618 -230261 -217416 106779 812669 721158 87328 -87554 107092 -218293 -55394 412651 513819 368444 -614052 -490605 -285177 144304 227533 -882525 445324 -122586 -406364 50006 -44234 -796664 -168704 577554 -946933 -354438 -796056 -428738 635170 354289 -457377 -960798 -418924 762925 -49289 396935 -63408 598329 524878 -195212 -668232 87229 35177 -34515 -513805 568946 172964 760344 -35462 -811249 -571028 652753 781964 940559 -710610 275021 -561296 832508 -834001 421720 920746 -884802 981678 -174288 -475144 387987 -942711 484436 -189718 233496 900345 -327962 -100716 65606 683317 383235 -578826 108740 -199520 -86162 495975 -831451 62910 -819192 -583989 -716423 969395 219449 127753 142529 -14…
Output: 15713

Constraints:

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

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