CT52734

Vesper Counts the registers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the monsoon port of Rainhaven, someone must document the rare sighting. This year the task falls to Vesper, armed only with the registers 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 <= 3994; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 2580 747329508 945905087 989833251 620122906 60685250 41593954 704818515 824134643 454694896 178809809 69108749 835638601 644448082 399461397 809392784 719427861 646167729 148629727 206705969 880015714 430566730 398879917 737896091 894933937 202455811 479419137 698041303 572765236 973133216 871112863 391770205 42671332 828541984 716949906 992223128 9129906 367563093 52463463 267393151 840584994 238116354 222444390 570387709 279113079 971160715 919901637 544712191 9949483 989385239 184723470 725162082 865642299 14590800 361933137 102867530 234099474 601412360 764146394 34996395 930615216 872531628 54779086 188301410 540740724 472958288 572304847 522797945 442932713 210590847 827030474 103373257 775739575 558066587 741447680 603903241 668587527 260586675 814528834 146138062 162746244 8466656…
Output: 1684605

Example 2:

Input: 1229 807 886 131 7 706 338 589 1002 711 1057 182 450 569 1065 705 1120 1217 690 1005 285 536 1125 1083 776 1004 700 208 576 1184 867 328 731 126 319 1031 1214 1155 494 567 204 1147 714 975 97 577 594 879 603 434 612 414 292 601 1115 18 1178 854 1082 645 828 750 496 400 222 521 541 974 1028 739 660 672 685 1152 147 92 470 345 1172 631 915 932 951 190 897 237 44 1014 578 592 749 634 68 506 56 1090 549 668 889 550 698 157 850 538 887 921 439 953 928 66 829 160 427 355 943 543 491 239 988 67 166 489 822 688 888 1006 95 1173 318 337 677 1194 920 196 205 153 781 694 1131 821 86 582 42 453 686 1012 174 271 347 443 161 665 674 109 197 477 374 350 650 73 1160 746 999 103 296 693 1026 820 170 830 1016 1165 203 474 704 480 169 88 1062 322 976 1061 465 551 176 1204 324 107 1091 254 1149 1171 85 167 99…
Output: 382928

Example 3:

Input: 3360 1828 1849 668 1165 2467 2534 1649 1870 3291 345 2213 273 2222 2294 531 1185 212 3281 3015 3303 2211 2085 3349 1497 1358 1594 1299 1201 507 3328 2568 1566 3163 2491 1187 831 2753 1437 1267 2726 2961 1871 2452 1481 222 556 512 526 1759 1234 608 2823 1099 3227 2687 2965 2580 2949 2994 542 2183 1119 1490 358 2394 3196 1312 945 433 3270 2374 1868 498 1772 1096 2251 1926 197 1836 1935 1033 586 712 1341 1445 1994 1124 234 3162 1959 1979 1069 998 1154 3116 1739 2076 1895 189 1111 847 1651 2616 2307 2863 3217 2023 305 1405 2223 3164 2356 2526 2127 1347 3079 1632 3255 1255 1468 491 1439 505 2232 2576 2329 3269 2334 1189 3093 1843 3352 1680 1875 298 1636 596 1698 2914 1477 3019 3286 2738 1303 1326 221 814 2928 2205 2161 753 993 2380 738 439 1817 1082 1884 3252 1990 1222 2098 413 1088 976 3067 61…
Output: 2889795

Constraints:

1 <= n <= 3994; 0 <= a[i],x <= 1000000000.

Loading...
Test Cases:No test cases
No test cases available.
Vesper Counts the registers - MEDIUM Coding Problem | CodeTikki