CT40496

The Disorder Count of Goldmeadow

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the trading post of Goldmeadow close for winter, Yash must finish the shelves ledger - one figure at a time. 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 <= 2771; 0 <= a[i],x <= 1000000.

Example 1:

Input: 1331 152975 378519 776278 977936 903781 414771 139552 532363 586378 302580 417190 473650 708424 348508 502372 613565 359276 578442 396 915761 938708 968924 272151 367076 683600 23628 96840 857479 853729 553106 923955 992308 363627 56983 640511 854389 902745 256897 41078 888008 29747 317536 950732 873298 90823 845300 977956 120327 509955 612596 556199 398436 119963 785516 913124 750639 624264 162473 966656 695153 913846 175470 575558 900750 579261 157516 57238 846523 555512 927022 2900 560964 225314 877143 158934 155209 262557 174584 263428 111823 872687 930602 722735 940199 832913 425835 474360 569476 872748 375806 98384 815885 87909 106421 982771 617984 250395 479164 977288 743198 953937 955947 791604 442606 82046 703294 207283 9624 990051 308279 349821 623328 366826 339084 799286 590842 …
Output: 447189

Example 2:

Input: 924 549050 51256 406880 880123 828152 101235 862099 735836 943728 187121 651654 621360 551141 167003 590753 892879 229872 416578 638093 500498 223984 991388 904934 744775 578258 980869 227238 527642 964032 104977 255144 557604 63650 738596 644698 406665 610863 459745 596325 715531 897946 258448 881449 952006 353784 11727 312239 919081 586079 439569 363784 838643 752721 102775 428839 797227 6037 830836 202448 968212 870770 34131 423795 945994 453254 494069 845723 847429 559333 530289 535565 932254 560833 642325 446863 606776 800585 797598 246099 4001 410596 16252 552665 751893 921999 86475 206883 719005 809120 587877 839930 347564 867161 942749 406847 156879 723216 319192 301173 284797 574181 401022 216302 508470 435998 29027 517043 928960 414531 347666 221570 748267 995862 343982 483968 34…
Output: 211273

Example 3:

Input: 1817 1225 568 274 573 1090 590 1452 1555 1104 1004 1155 33 571 1651 1727 1643 796 222 440 724 506 729 806 59 978 1098 696 120 81 541 745 1712 705 948 186 566 799 1236 548 1680 393 1659 1640 1217 1387 553 281 1302 1530 389 432 671 651 1496 402 93 1460 1732 364 990 1142 880 1642 1328 1757 1562 37 136 446 908 1014 525 760 1578 1131 1333 160 1281 1064 318 87 767 1524 435 1218 453 962 1048 1072 1406 716 68 890 787 550 1163 1456 512 484 1652 1160 964 966 1446 476 592 670 627 643 924 1050 46 269 485 1723 421 156 823 1447 1159 415 314 298 392 1351 844 109 493 1322 227 1402 1398 82 1509 366 1348 676 1498 385 981 376 1397 1671 265 1461 1768 287 1021 1026 1806 1593 185 400 455 342 1528 280 445 1638 26 70 1463 135 6 1799 1522 1508 388 1331 56 1424 1812 961 1759 1253 1791 934 1807 608 1645 1374 365 390…
Output: 814564

Constraints:

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

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