CT65233

Seth's Ledger of registers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Morning light hits the snowberry thicket of Winterholt as Seth unrolls the day's manifest of registers. The tally will decide the next shipment. 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 <= 1842; 0 <= a[i],x <= 1000000.

Example 1:

Input: 1422 692 624 246 169 1336 121 111 860 105 1199 972 1272 679 785 228 657 751 94 631 691 359 405 907 765 990 619 569 445 978 127 786 887 128 1015 1127 546 1150 908 1170 1300 1052 164 522 772 835 579 1334 1312 1400 790 1266 523 495 517 636 814 229 678 1232 834 1123 1246 1322 767 106 1286 322 547 842 97 1393 147 263 1107 425 799 925 1289 873 778 382 502 1204 158 725 110 375 1372 952 272 872 664 1016 595 451 1267 1263 1088 943 360 336 221 950 188 152 1391 736 729 1168 213 571 82 833 1011 348 1207 1218 222 27 929 1143 452 802 899 107 548 942 447 282 1288 1071 224 1136 554 698 67 215 739 112 922 1213 1394 1113 480 562 1054 295 784 634 277 1117 1264 1381 1397 1067 204 597 755 902 1145 46 973 155 1270 50 971 184 771 1009 1026 909 1068 743 521 1013 1008 415 1221 1169 793 1031 658 247 1292 216 840 60…
Output: 495329

Example 2:

Input: 1024 627957 421626 287589 221012 957813 606227 361813 18432 743381 761857 682826 29438 640944 323076 272820 107603 626830 169727 711202 132380 107289 937701 81408 675976 456790 881162 946645 929890 85614 285103 718631 247407 443060 183208 80409 890647 345082 29723 80381 199191 396744 183767 764620 903045 944513 834042 681011 475996 659792 645344 755579 142414 688822 958236 489122 81912 945688 240898 745463 198414 212400 357321 820444 163639 516554 275945 675024 995754 561557 420279 352842 663942 356552 930099 500996 117055 332998 382680 272633 840376 630472 310236 975873 202215 343486 508988 655997 676900 49602 990756 159667 711791 693589 851472 382196 896658 543189 64249 539967 878283 540638 835641 712697 689656 164093 31659 504113 622195 246844 159090 972782 909648 684121 968331 461337 8…
Output: 263627

Example 3:

Input: 1786 296059 752325 140263 607342 793903 900793 84669 383672 30361 602364 109214 418069 247302 650744 28028 261160 433100 594783 363214 78805 677786 486931 639965 240260 699921 106933 329181 848482 208876 678641 990491 822482 958941 936192 852064 974419 610553 390313 975211 903280 933468 674999 518194 765440 443090 843914 129584 26748 546636 606348 40534 478802 714435 449667 453615 450211 760767 930205 428617 327024 494703 464213 672194 373328 740522 450079 129967 617155 535670 257807 489552 122833 331356 997779 715962 998712 494560 799755 245766 224768 306830 679937 195300 237797 18304 719386 41053 60862 352089 102620 800192 450591 303739 922735 158719 304707 252186 688242 672112 315533 116477 245781 945298 414603 62257 300354 514327 314196 690131 694267 330679 512003 88859 639155 572680 3…
Output: 798389

Constraints:

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

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