CT42010

Jaya's Ledger of vials

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the valley of Misthollow, someone must settle a dispute between crews. This year the task falls to Jaya, armed only with the vials 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 <= 1600; 0 <= a[i],x <= 1000000.

Example 1:

Input: 1061 411573 59680 517092 944912 164906 455828 328924 503231 763173 645289 850163 498436 669471 333658 949935 40999 443499 215810 319201 385717 285352 567643 298553 159004 513102 431536 283046 246005 467695 257072 412402 374657 309403 179058 387810 692751 758648 869935 699369 460762 896173 892134 5219 431449 872592 365982 795769 184517 957628 523951 468534 347860 41495 454160 210319 56114 264751 818226 740052 610556 919856 380113 452123 825970 170761 256103 605208 214413 131419 354171 867572 597996 587811 329653 889189 797496 568171 908227 32056 470956 847858 63117 793582 669605 924356 252107 359224 961617 413406 973502 68519 439051 489144 948649 51581 113673 906377 314486 207728 558412 314379 519428 114348 806480 39691 400376 264671 617299 893628 848425 960965 571695 515008 128875 328440 6…
Output: 288731

Example 2:

Input: 1399 275480 926163 737973 502002 242875 583461 704674 180519 984309 122337 365491 185937 660606 979039 535980 340564 486355 827539 279185 105270 255732 631220 660065 803675 884071 774183 292917 821858 258382 995325 6988 583753 334868 822451 885339 358480 148391 771357 992071 217712 356910 467367 36675 154504 67340 836655 131332 927511 257134 383915 627934 123668 523650 155447 286871 183778 835153 141294 256936 322052 749487 248407 33778 387910 900468 447694 646006 552798 736433 97681 887581 632592 523632 930462 318629 399825 874943 338052 63092 153673 259350 315859 996199 336823 273322 104704 100821 499961 400666 904705 907381 242621 449385 644075 703762 669676 426025 590613 724041 766597 185284 778596 715081 468585 344722 399329 674608 509963 191586 208492 123816 493029 880787 922180 6862…
Output: 491993

Example 3:

Input: 1511 108567 124153 716751 138781 95881 140676 622878 880952 780140 257636 590751 196730 491778 52155 563966 727158 290193 508124 433474 746399 503470 953661 473536 397811 30686 848296 190302 714809 880014 583985 176731 230804 2981 948829 822740 740588 545330 26653 995287 451897 785222 122116 211489 451425 489364 874630 730822 715529 637444 710137 59588 35149 953287 357479 310995 587030 189571 842077 211012 586431 895853 363959 298128 460965 374580 263981 526560 573183 892456 132186 981438 546071 350855 282395 619132 898239 584360 988606 940461 16060 57449 14706 426441 352595 580923 485610 365344 903656 678868 890459 772313 599663 549084 585462 428625 296740 595465 996404 422489 920047 395516 274069 580755 160173 220155 679514 487851 448942 938629 493783 874209 893423 484235 445555 812287 6…
Output: 569297

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Jaya's Ledger of vials - MEDIUM Coding Problem | CodeTikki