CT38795

Lara and the Sterling ledgers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Lara runs the customs house at the lily shoals of Padmore. Today the books show a list of ledgers, 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 <= 1541; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 935 743862 333335 593775 239472 -871574 -263303 772090 -707333 855177 -154498 835807 878627 476533 -770707 -396468 411324 935419 409942 -945764 432383 325875 52037 338618 -763895 -637369 -499513 -960133 -496976 131294 244387 915663 456943 -548817 259622 -379364 -402896 675569 -846350 -907196 -2168 -636927 882199 494295 -705675 757670 -563243 452081 -889564 -690838 632472 173593 -365775 250956 -163248 671445 861507 -78151 927368 347089 -664921 679870 36944 326005 252192 112854 -393617 1460 -534507 833021 542448 -116782 -310461 -826570 638135 764800 -57033 812224 -414042 -681330 -594882 -846548 -545713 520579 338267 -46911 371991 -67257 84961 786268 231491 -571199 827466 918458 -428918 699146 53619 666728 929578 576338 395702 -957351 -487803 672015 218573 421599 -61999 -459810 168331 -56859 …
Output: 221900

Example 2:

Input: 823 194 523 761 538 554 175 816 263 33 169 190 555 104 360 345 250 732 243 138 216 747 738 696 173 813 46 375 694 743 744 114 680 201 380 388 272 522 121 235 515 737 246 34 821 806 472 750 641 311 619 620 710 421 536 687 799 727 606 464 223 339 682 546 168 427 593 239 130 514 423 191 233 324 453 402 361 343 368 449 468 358 163 111 105 296 595 167 525 596 69 647 443 153 437 742 154 41 588 18 790 62 773 736 530 24 669 817 195 420 112 481 510 458 172 417 10 776 457 450 197 757 492 255 557 287 658 459 486 140 577 372 729 811 316 166 691 28 809 94 204 439 295 269 535 164 475 254 123 259 209 815 478 746 752 409 599 673 533 772 592 318 14 807 518 519 359 566 810 283 565 266 553 25 11 349 426 717 573 64 558 432 674 784 334 612 675 160 308 543 139 705 466 454 610 502 635 613 766 286 718 435 184 227…
Output: 172880

Example 3:

Input: 507 308513 -608038 -795683 -508423 -715800 396423 -517776 -166498 -793216 92789 260548 -641786 -779263 -416584 597092 308301 -393144 556392 -482861 154065 -177676 205083 -594982 -118774 -580519 558357 898818 502394 530152 784635 952895 721799 -506073 -291525 -434743 110756 -142367 896555 -852647 373102 435608 -421363 -607502 309618 -493562 174668 168962 -419602 -302138 905673 352626 -714531 517920 934287 -375742 220372 -888378 504469 -364019 388067 155401 359289 -304129 170844 -757358 -982695 228940 -812777 -854572 -400804 -370713 111337 -857990 255758 -298446 -749315 498935 500799 856185 713039 -498514 629149 -574668 786141 183113 729233 294802 -14792 4395 229768 -149697 -551973 -336285 118378 168304 866527 613137 18989 -776185 862021 347337 -492778 -227101 -418430 -775986 -834483 107812 …
Output: 61143

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Lara and the Sterling ledgers - MEDIUM Coding Problem | CodeTikki