CT38195

Vera's Jade Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Vera the factor watches over the clockwork quarter of Gearford's stores of ledgers. A careful computation stands between order and chaos. 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 <= 3580; 0 <= a[i],x <= 1000000.

Example 1:

Input: 1723 504 406 430 1509 310 760 291 122 636 1439 1254 377 402 839 728 404 469 1122 743 727 605 1137 1354 618 1026 1176 763 1253 1267 172 211 1705 821 1263 259 1614 1620 345 1673 42 1596 1652 1462 467 1607 1392 343 212 368 555 380 372 705 1021 287 1698 885 508 620 1341 665 574 718 585 244 326 1062 1274 1272 830 414 963 1568 205 170 932 580 364 1353 0 1271 1076 1512 1054 1707 367 1440 717 1656 450 1659 1393 154 604 930 1225 1402 1121 1715 1606 318 1447 1096 1194 316 454 1488 171 1164 1494 1591 132 438 1536 960 238 233 1455 1416 1039 956 107 748 754 1468 609 890 520 1523 299 92 1342 1061 1565 1537 1347 413 1712 305 772 36 1204 1279 3 1541 214 317 617 688 1423 266 516 1562 186 601 333 1314 725 896 579 462 992 1160 1627 921 1491 1273 52 860 1720 844 27 1481 556 1213 1165 488 134 242 329 825 1703 …
Output: 758304

Example 2:

Input: 467 137449 138629 767595 230674 319366 202208 500250 209912 474232 654041 221254 952343 735348 636232 589287 297046 529277 51756 48702 422164 63979 933735 117162 18215 118145 102073 346367 431342 290311 606 342743 641251 34761 223255 359300 223745 586777 841044 251663 633676 803257 85128 230496 160544 80281 672595 6516 797692 607609 112311 50571 292865 32406 633632 585882 928950 382737 626529 690863 908395 84558 135049 988508 935619 477330 903532 490003 582287 313608 966182 45317 742010 995579 335207 252736 997078 551789 31278 14928 890539 882493 523399 674940 163244 181277 707220 451369 553800 628601 266286 962279 341412 306095 833977 419226 188760 887115 181357 435043 204920 432720 600666 231782 43004 189126 86926 584072 888563 354002 504366 747817 116381 970272 675100 506432 987736 4456…
Output: 53383

Example 3:

Input: 1954 1573 190 52 134 812 1844 1086 1697 773 219 459 156 1588 1937 505 204 34 24 269 1475 591 601 1613 733 173 149 548 1177 1415 1621 766 150 1753 186 1036 1474 302 1093 1435 950 1947 104 619 502 327 1872 1731 630 1007 539 597 351 230 636 1480 702 1310 1904 860 1271 1126 116 816 1051 214 631 1585 738 3 420 1322 1780 1591 141 953 211 639 241 842 607 1236 1195 730 325 1634 333 612 1141 264 932 341 984 1936 1261 1090 376 1207 1593 740 560 250 1324 377 97 1808 769 432 742 802 207 1687 963 291 1297 1323 1490 897 1563 1063 1742 969 1138 378 1503 93 60 552 458 1385 891 1665 1159 1396 827 776 1030 411 884 265 64 454 1655 1684 251 336 1375 1470 1453 1664 441 1774 949 1028 1825 758 1055 868 467 113 1625 431 198 675 1369 398 417 532 390 1599 979 637 1538 883 1293 307 1882 991 1794 297 1243 1425 1854 4…
Output: 948119

Constraints:

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

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