CT60735

Yami and the Disorder Count

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Before the gates of the lantern district of Glowfen close for winter, Yami must finish the crates 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 <= 3162; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 1600 359 1512 1124 887 508 918 822 793 1467 366 994 280 1340 431 23 1238 350 287 397 914 106 693 1478 1567 1420 1443 1242 339 882 17 47 1581 209 744 1414 55 325 532 1176 308 490 1234 832 384 925 306 1453 1595 302 1374 34 1156 929 919 556 1513 133 483 438 807 641 1035 12 671 1127 1584 1428 1093 1194 1351 333 108 943 1296 1364 819 898 795 662 580 667 1280 157 383 1349 87 790 45 435 617 1102 748 1152 179 1182 1090 623 285 1413 817 829 1084 1144 1585 193 756 1008 312 1053 1497 653 322 553 903 1248 1187 70 1553 849 365 669 1335 247 993 104 1083 635 1560 758 668 1599 621 1260 1163 278 260 940 557 969 876 525 123 560 1075 1318 965 722 211 4 341 699 284 152 1479 370 25 1393 754 1245 304 1100 269 995 907 1112 1375 986 620 958 44 1587 1542 922 295 320 657 917 644 825 1073 614 1293 466 432 1532 996 1…
Output: 650486

Example 2:

Input: 1389 516 237 870 793 532 899 131 1169 118 950 522 860 281 625 1 588 868 1153 495 309 1184 648 833 494 1374 21 981 546 986 196 779 799 1089 142 605 277 326 544 1263 918 289 838 816 539 1168 906 1065 1139 659 609 758 1367 1227 1356 60 1254 191 102 1351 900 239 243 108 496 1290 752 477 568 863 302 465 859 957 1102 1144 925 1205 1103 352 1012 183 1195 644 910 1159 1287 930 279 410 680 690 956 558 1041 1343 858 38 80 1251 382 541 1327 856 1054 854 518 624 755 120 785 402 848 362 739 594 1291 1345 760 51 152 940 272 603 501 1222 841 45 935 90 613 1300 676 815 1308 1200 370 338 1052 1091 346 18 992 1187 132 1289 446 469 28 478 293 1337 696 159 1207 788 95 1082 668 972 1120 359 1341 1123 57 826 861 770 7 1105 1273 1258 1042 231 78 348 527 716 192 1352 1136 1357 1218 801 1040 1048 880 920 144 596 6…
Output: 493131

Example 3:

Input: 366 983123719 250871781 664036136 308053121 920711332 441950642 426065639 691647732 804991009 235737533 692714708 633332084 833672642 974335057 975937884 489019613 908417839 586268676 784574706 991064828 287715222 825286451 582676593 519713581 985001902 833603928 490431849 805190952 736437922 898945026 163480647 521170994 643320399 251654802 137175468 71313712 305009879 668776107 67674262 600420865 120199906 254785325 377434290 538762410 847943957 197982595 589529612 317293798 508105693 412111765 401184158 445926538 673508820 101764380 923681986 425671186 560659943 186246813 173347179 892128128 925106490 389985745 534300402 362368367 801568304 40788696 88777509 751552299 28476235 589405221 241615657 827537566 333006759 470530242 695165725 134293279 374141582 430351316 809181310 664252752 9…
Output: 33115

Constraints:

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

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