CT48958

Ivo's Ashen Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the cork grove of Barkhaven. Ivo spreads the ledgers records across the table and picks up a sharp pencil. 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 <= 1278; 0 <= a[i],x <= 1000000.

Example 1:

Input: 908 213366 553505 23497 192297 779885 830507 963388 525754 524275 936296 615826 789848 944916 270840 115779 877236 218167 203906 766709 148755 257424 405310 812935 345187 664300 230647 643392 423638 227904 38989 700747 488060 812256 644960 291506 576066 892019 787070 266178 886525 942246 481255 547652 655886 443893 174829 750572 539434 845363 438910 77562 960248 280520 613397 654127 644000 184630 944298 50965 26720 41322 120802 162568 453084 709380 859427 275858 541834 737510 544309 83423 675010 866158 689214 820196 548707 471408 801166 586546 45431 775228 655906 32091 458639 471286 915151 526212 376870 790752 537498 356203 971809 190040 495053 217206 638408 143645 280547 613335 611506 935916 872954 644238 659966 766912 422105 71805 403854 561171 330036 886321 851019 372724 564938 280880 3…
Output: 212097

Example 2:

Input: 691 301 300 433 327 265 153 91 368 664 618 167 4 146 294 216 127 197 685 17 520 27 215 666 120 383 41 107 236 278 429 455 343 335 28 487 662 255 572 382 609 200 175 493 627 587 116 38 121 95 571 315 518 203 352 63 31 53 551 254 317 526 108 226 20 417 481 271 386 126 628 567 510 641 373 684 119 256 196 29 79 333 397 150 66 459 686 559 375 193 163 649 192 244 263 464 650 384 206 110 525 409 542 201 194 204 207 209 296 166 689 395 492 49 221 274 561 355 519 86 264 437 496 74 425 472 468 405 416 205 319 297 19 533 635 224 413 92 30 347 325 676 415 480 336 184 295 556 453 266 408 152 43 474 350 310 388 88 584 231 123 21 633 502 652 298 371 490 399 389 681 242 463 312 528 661 136 400 54 424 3 141 306 575 223 45 646 585 282 122 106 109 674 195 228 524 643 173 97 570 185 512 622 273 172 217 539 44…
Output: 115631

Example 3:

Input: 59 30 53 54 57 48 43 26 50 36 8 35 22 0 37 16 52 17 40 23 14 41 11 1 58 25 28 46 21 33 5 38 39 42 31 27 7 56 9 12 32 4 20 6 34 47 45 15 13 44 49 24 18 3 51 2 29 55 19 10
Output: 985

Constraints:

1 <= n <= 1278; 0 <= a[i],x <= 1000000.

Loading...
Test Cases:No test cases
No test cases available.
Ivo's Ashen Ledger - MEDIUM Coding Problem | CodeTikki