CT58306

The Teal Disorder Count

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The registry keeper Cora has been asked to optimize the storeroom layout. On the desk lies a long table of ledgers readings. 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 <= 3822; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 2609 521 58 2603 2055 771 866 1862 704 2183 166 2060 2394 464 79 1101 183 463 504 2290 2150 12 2348 1483 1358 341 855 447 2568 2551 1591 1482 1476 358 22 626 2370 734 1354 1587 584 611 1448 1796 2253 491 1579 847 1529 503 890 1298 33 144 2052 1509 2446 699 2146 1059 924 1768 155 1089 30 623 818 2288 902 1272 394 1297 1305 2030 1264 750 75 1431 1153 257 828 1603 1953 1375 543 2126 246 1263 389 2279 2460 1335 218 225 728 662 1062 1485 2085 2442 555 2466 2168 1523 1635 2318 163 2293 1601 1748 2530 230 264 2172 1393 251 1462 2444 871 2169 1188 942 567 1212 1444 189 926 587 2012 213 1620 1698 1981 44 2027 2578 667 1493 64 2429 1946 1543 1043 654 2353 799 2304 1967 1463 838 1545 1162 842 707 2339 1765 510 1239 207 1578 1662 1874 480 1864 2505 369 2291 97 2480 826 953 2342 1120 304 2376 2162 2057…
Output: 1714252

Example 2:

Input: 3016 1493 1182 1657 2159 844 457 621 1339 640 566 1743 2519 545 2805 810 157 1658 286 955 2949 2434 2268 1102 300 1387 868 2276 3014 1986 2260 2323 2296 1940 750 1138 330 843 2479 2139 602 2843 916 605 74 2247 703 910 2948 1433 1046 875 534 601 1370 130 332 70 2753 2910 68 1891 1801 959 2021 842 2264 2794 1094 743 1488 1325 327 342 1263 2996 1693 2782 311 2302 147 571 2018 1522 158 1268 1277 1349 339 2977 417 1750 1454 1352 1251 1213 1509 31 2946 1466 346 1070 1747 2818 492 741 1228 845 795 2720 1561 26 2506 512 2126 2085 581 2176 402 2025 1946 1552 223 174 383 2952 1288 2646 184 2894 2324 1691 1101 1843 2528 751 474 2771 1518 400 676 1935 960 1144 1069 1854 277 452 1802 273 186 39 2279 2829 661 2917 2596 519 2087 79 1735 1168 2461 1531 2781 914 2338 2833 285 1634 238 2589 1383 2701 2421 1…
Output: 2252862

Example 3:

Input: 596 256241676 573981453 129723565 610222663 532121902 511810117 29718576 220919445 992465884 149796177 673770277 958871966 133788858 431248703 188992641 679407177 261623686 47358102 555448948 459348122 278655068 199151319 188291153 853818229 698525777 77172618 963225154 993925782 511941256 767698552 986144971 943270182 405877524 825909416 277479097 778869518 351077895 957191683 192236320 438977663 825858359 194429161 640305921 183242164 374348134 280901238 879779171 457318455 607953355 825302316 84741759 448980359 22514337 95013360 804620414 768904939 369072415 380953146 306564258 917373899 68313823 839324032 951201497 164380602 855617998 176701301 242617776 659862290 189490709 160703413 772546667 588488904 175350781 883341190 993879505 918278398 870701680 983230392 80353675 2253444 342654…
Output: 85558

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Teal Disorder Count - MEDIUM Coding Problem | CodeTikki