CT54135

Librarian and the Timeworn ledgers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the railway depot of Cinderline. Librarian 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 <= 1734; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 1452 -122625 -878137 -672620 -165019 553260 -346662 158485 936601 723650 -653751 871881 880589 -850325 -26065 -974501 966176 -516887 745816 -704411 389615 179838 661795 -608077 818448 424744 -723389 897275 332416 -352871 525451 -98755 724003 114201 -525532 -368132 -457915 -232960 65185 76487 781655 -505608 -569089 783370 184901 -361993 -66130 877710 -760635 -351703 597839 -704594 341173 672205 331735 -500779 -135938 -844200 970350 459397 -644942 -659352 130414 -311557 -184775 -96641 -416810 -274765 -921814 -386199 -210914 -797365 -729253 -810514 838254 341689 -123219 716780 -17916 727445 742087 -739724 68718 303241 -234543 -800425 -967721 771388 -374800 -110213 -603290 -936321 408936 -756570 549105 249904 671664 -800799 -550579 75451 485304 -5176 67852 -896333 -213197 -872247 138355 994524…
Output: 512445

Example 2:

Input: 162 -216532 -615605 832836 142955 -830882 -807287 -729697 669761 -342054 -625773 -868604 17484 310583 419865 -620412 -986903 -2447 891988 -69925 -851398 334625 907988 -305464 549591 190595 994521 -873311 -475823 942712 -810554 -652094 429091 -970986 -933961 943525 757364 459115 627097 345744 850956 -741270 -962132 309858 -519581 783756 -249256 -33346 -391221 117263 -425239 -801756 833685 -107243 498366 629850 -364980 -812748 367000 -688480 936563 946027 -341764 -926232 954942 233960 406216 447378 617624 446949 968424 993955 510334 456646 553103 61301 429010 -364543 -643148 -263869 341416 -858648 -179763 149530 695483 635360 526438 884321 293968 726777 -248994 99497 -23639 532665 239376 877313 -527962 580559 -501608 -835557 297980 -671722 -742161 789731 -10825 -688681 -385903 287252 930698 …
Output: 6511

Example 3:

Input: 1611 142549 -65584 315283 -426597 -515133 502664 -212 -638417 -410293 179262 214844 -233792 -833782 92048 526465 467698 194739 449446 -663515 -196213 210115 104216 731370 722210 623884 -314802 888468 -468581 -941210 662141 418548 -111063 -167318 705962 111307 696814 -441812 -954010 545130 515464 443049 385476 598417 -579250 -461857 90449 613905 -65781 -480530 -169497 -983976 301723 -917689 40332 223057 -702180 376333 447146 -331956 73010 328268 203485 276104 519836 466316 805500 -196136 806611 -118859 421539 -995217 758906 555652 -924047 -420743 878668 -591719 -861799 -763698 959688 -965116 -557328 -122466 -335382 825097 609789 610040 -436929 -369479 -279147 -893425 37070 578906 528209 528333 -240040 300119 -191387 -180674 -992345 -537944 -755009 165979 -760942 856861 166921 128934 -201072…
Output: 646047

Constraints:

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

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