CT60511

The Disorder Count at Stillwater

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Every season at the crane marshes of Stillwater, someone must tally the donation drive. This year the task falls to Devi, armed only with the weights register. 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 <= 1877; 0 <= a[i],x <= 1000000.

Example 1:

Input: 542 357891 77867 364765 366197 571729 271438 870329 207266 292474 198755 772033 895980 23391 451909 92074 401349 194181 787790 119595 72212 712636 425065 371616 220349 861864 592446 482430 902118 999679 136144 69317 422777 848315 911685 840815 119255 308557 300549 181728 524363 400072 89373 25873 931137 331427 875981 65359 194433 908764 331528 143516 423065 704130 486894 559759 47933 277455 727800 103469 950081 882320 359523 419413 172332 768639 379665 282296 957415 592215 884696 579437 201081 593632 792085 966370 611778 234655 833452 30720 936826 26724 318458 990044 200554 752533 401245 477768 234151 564697 994173 353529 602915 309213 175711 947983 841463 992873 542125 443232 278942 854391 342946 521467 89058 749385 395378 352068 347682 418823 831930 920351 407638 359433 311716 979492 732…
Output: 70837

Example 2:

Input: 1302 932057 686731 127414 470778 828886 841577 966340 946879 596454 339631 446258 154266 336261 890478 31097 96495 900645 535495 31623 969024 866674 678963 599501 366331 261776 299919 266226 466371 832194 543430 290062 370551 344225 296412 632787 892080 753706 450960 662174 745832 73046 530725 177766 838993 404667 44111 750456 736201 410090 716882 579502 11841 719844 758946 679261 478963 450676 670626 456042 48209 201406 455367 956479 995962 478122 29610 295573 872426 478788 98193 478527 672799 393368 334184 546425 204284 957246 614627 105768 716914 408715 418055 582801 504929 673180 419146 739507 738661 427157 660785 461701 860330 281926 946885 47378 768957 468427 858296 432278 728364 222435 470155 932646 614261 341191 286729 361352 404845 168761 293506 924885 361666 415467 755108 958929 …
Output: 413716

Example 3:

Input: 1173 699 866 295 814 784 649 744 1042 780 94 412 1077 131 1008 1099 594 1028 768 1064 277 579 972 900 583 1127 1059 994 1144 786 123 989 111 224 896 229 1083 739 1152 1167 292 855 664 877 436 763 151 963 517 953 769 74 56 24 121 252 347 523 146 293 230 996 613 253 940 1170 512 191 1074 31 351 638 1160 363 707 559 616 364 513 930 885 381 615 410 474 402 39 622 687 1013 539 534 1128 71 356 528 1162 314 255 897 921 825 460 250 1088 306 185 157 1045 1041 841 429 593 102 948 1090 907 1009 1137 192 847 710 237 296 828 150 233 1159 911 682 332 619 954 408 294 148 626 1138 189 241 831 614 284 1004 256 1150 906 909 867 325 683 49 467 913 956 912 365 985 826 37 311 543 343 163 109 380 205 378 377 860 12 717 439 980 276 83 868 208 501 781 783 673 251 236 171 1146 244 716 348 995 497 371 455 680 765 7…
Output: 348185

Constraints:

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

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