CT57619

Draper and the Disorder Count

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the singing sands of Echo Dunes opens only for a perfect tally of shelves. Draper means to find out. 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 <= 2433; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 939 169 153 704 837 376 444 579 143 767 372 362 903 803 864 638 824 451 320 426 448 409 332 684 316 617 427 697 82 173 323 858 188 745 472 433 731 527 934 251 112 808 333 735 487 0 806 773 766 736 573 583 76 57 829 176 15 12 411 759 910 591 354 546 777 8 228 283 230 339 1 386 279 586 92 600 53 893 441 902 238 43 623 220 516 828 798 924 900 577 718 89 274 551 142 177 265 894 681 236 841 836 464 827 98 393 713 474 647 811 125 102 738 285 447 151 234 342 358 78 672 357 88 90 833 440 757 755 589 678 149 392 909 660 835 717 604 762 380 563 35 915 526 431 511 506 255 716 669 884 215 730 505 156 851 407 652 769 359 470 645 267 480 590 522 421 653 908 217 381 926 752 869 531 555 270 218 206 855 280 557 928 796 825 565 865 493 229 857 63 843 109 121 624 54 388 262 923 329 404 141 29 879 785 723 428…
Output: 224314

Example 2:

Input: 1735 312 186 1612 57 885 325 776 1245 1391 89 44 744 775 1713 909 984 281 657 841 915 318 982 651 948 434 1733 327 399 1072 634 1285 763 1339 778 1701 1617 868 1443 1494 992 191 1653 1580 1345 1188 1315 496 213 1732 738 1090 1540 958 1207 594 709 720 771 1212 1344 1040 139 787 78 406 1070 756 384 1421 333 1297 1273 624 1331 1646 1584 1675 1662 917 1269 1125 630 1476 632 1710 774 112 1198 1410 156 897 1605 551 1062 344 301 258 704 848 1014 1317 1385 1625 1695 1516 358 1322 1588 1059 97 1173 782 1024 1343 1549 1669 336 85 279 560 615 169 973 1206 956 1656 576 1524 1052 1019 1407 1253 305 313 929 525 146 1541 21 876 277 353 1238 1514 1068 762 153 1723 896 555 306 50 237 814 835 1448 377 1340 1475 1586 1166 1360 293 130 1431 574 271 1460 1724 1694 383 1303 1063 256 1661 731 1323 645 837 718 10…
Output: 762236

Example 3:

Input: 1147 975854262 774088715 196879892 573052534 431770360 135067750 331370199 271202353 513935349 91845883 332151143 185115252 607476457 143901687 532731947 532400610 973523260 417313034 647784309 330842106 938557987 549684509 140108112 931140770 513729158 294542239 358560945 57618495 146773281 514835820 945317768 249627802 612233987 611782752 946600982 580820831 616825064 152069381 161237427 662794237 201467399 419995075 910110208 842473396 605639164 336397869 710501347 634881347 892078769 694468910 639270928 312184829 510450532 844950738 445780847 375088951 809109161 487354859 846267449 606032535 817419728 209348678 146639227 923541983 416621837 62671835 740403340 292665853 519464406 804802362 431329758 78718986 534027543 749428412 136288256 735059066 60991838 190438493 524007594 743610230 …
Output: 325129

Constraints:

1 <= n <= 2433; -1000000 <= a[i],x <= 1000000000.

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