CT43306

Last ledgers of Uma

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morning light hits the opal reefs of Shimmerdeep as Uma unrolls the day's manifest of ledgers. 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 <= 3604; 0 <= a[i],x <= 1000000.

Example 1:

Input: 2604 928 22 1963 1375 2245 800 2258 300 404 1933 2326 834 1510 1105 1584 2294 2059 1540 2452 1094 2054 1639 1153 2513 1106 863 223 904 943 2140 1720 1424 1501 271 940 137 154 2535 322 2428 827 1272 1349 674 1421 1339 508 2546 951 1769 419 1692 493 895 2070 321 2208 1415 233 2026 1306 2244 195 1422 1284 913 1366 179 1691 1908 691 480 2088 1144 1381 60 2463 2510 1604 1842 1934 784 2529 1542 330 1419 1813 1831 2256 1356 1902 1301 1713 839 1149 1887 2497 1302 12 1246 772 1794 146 1416 471 487 1818 776 919 811 1347 2066 1004 537 2440 1754 1861 398 483 2104 2285 2475 1278 1067 214 486 2006 1551 2516 2399 323 2101 2601 733 1019 1456 2518 1919 2496 1297 2545 768 2448 428 388 447 2444 1992 711 2108 1898 2509 1500 2204 1410 2169 1728 1871 738 1941 2253 150 2209 191 2260 932 799 1614 1895 954 2271 17…
Output: 1724175

Example 2:

Input: 1433 65 1142 768 825 50 479 912 1312 1072 877 434 54 947 1241 785 60 763 775 1147 370 1385 1008 41 816 1325 706 610 948 398 455 837 1218 691 667 143 428 1034 1354 1048 757 576 842 255 601 879 151 1137 1105 147 1083 751 1246 1337 379 1401 913 729 363 352 1406 1213 618 796 1405 15 584 62 869 198 834 818 408 32 160 1050 130 1216 1115 851 1329 1086 1052 993 410 896 1004 69 510 229 1273 7 79 861 1110 1088 990 118 970 19 141 1330 1402 1029 1282 1305 767 1209 583 270 500 360 951 391 323 1276 1025 1011 128 755 823 230 1117 240 1386 267 898 340 671 1411 720 477 1186 1310 582 181 509 142 848 466 649 78 152 554 1134 980 427 275 602 960 760 738 369 714 138 712 570 1085 693 294 1317 1416 129 1254 315 934 1163 847 619 120 156 1284 1182 467 364 1319 11 299 38 994 149 486 283 257 899 1199 673 314 259 777 …
Output: 511390

Example 3:

Input: 1441 887405 167460 217248 349552 710709 762637 49882 836251 591977 579241 310680 684420 809670 94518 625552 854547 325273 288931 149509 881210 26513 970360 393019 126292 346553 532454 46620 391298 598586 627387 883445 346703 626511 366541 264526 892256 562805 759253 571491 933207 11207 49976 466103 375443 439894 176179 381950 844657 293973 362071 479940 657448 322887 708049 553872 75333 177971 58486 817668 175446 103641 990139 71058 225105 801947 102339 576273 147713 363191 252585 927085 346115 351867 460604 98120 1738 54275 806336 966533 267706 700073 780411 533588 419945 431640 471572 397581 27802 245693 392956 598524 379770 842433 186993 757296 935721 663346 8120 773168 34253 72057 988442 442231 807757 320101 382112 169029 833291 512216 362624 697939 75554 396115 800334 410030 717790 95…
Output: 507693

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.