CT64982

Trader's Ember shelves

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the cinnabar mines of Vermilion, Trader records each shelves in a worn leather ledger. The guild wants answers, not guesses. 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 <= 3316; 0 <= a[i],x <= 1000000.

Example 1:

Input: 1257 592 847 355 188 833 210 1134 511 575 1231 336 12 142 1139 744 243 912 1023 13 1056 746 1044 206 631 849 621 591 669 1080 661 1101 579 816 22 743 1196 1222 248 1156 1189 417 437 1132 806 1168 1163 548 767 544 6 848 32 886 435 1114 499 290 296 508 152 750 1128 1205 1226 459 365 788 135 222 983 578 1016 163 451 759 1051 1102 583 486 1249 458 1071 196 736 876 524 932 926 1174 1169 1082 722 959 424 1066 681 193 35 791 1112 305 335 312 536 337 1109 446 1248 831 1063 82 25 683 85 293 421 1227 1021 1232 228 699 1152 137 244 1218 168 367 266 558 88 370 364 1042 893 888 224 1216 1237 294 1210 887 199 784 822 761 1088 719 60 217 1100 1127 781 902 448 608 875 464 20 64 112 1028 16 657 301 547 1117 987 73 557 644 179 1170 677 618 749 834 472 277 54 947 287 630 268 861 412 438 651 134 326 724 476 3…
Output: 402821

Example 2:

Input: 1029 100 862 69 976 264 650 467 335 240 572 429 605 422 350 413 1016 1015 625 378 64 888 567 645 643 1010 465 654 173 940 148 973 418 651 644 445 373 565 227 26 943 904 155 966 615 789 202 886 435 977 954 281 201 950 357 819 141 52 119 255 33 1017 406 327 889 913 228 93 971 476 337 391 32 108 231 521 846 854 717 681 741 801 608 460 424 979 330 767 958 21 502 852 273 941 490 937 548 347 349 938 947 863 549 531 590 675 855 184 556 196 642 321 931 214 271 306 477 67 622 53 1002 629 623 18 472 258 805 305 849 241 479 626 969 636 840 935 462 174 158 276 964 722 430 355 509 235 208 323 978 210 290 746 340 610 533 576 841 1018 129 756 646 804 771 914 790 295 1006 832 815 861 994 618 637 488 504 881 285 401 246 204 713 503 253 187 584 630 1012 60 750 621 47 289 985 229 772 143 688 92 134 40 120 73…
Output: 275153

Example 3:

Input: 794 931890 158040 541122 797803 406720 914370 787115 714178 515969 924410 222894 622023 598981 170872 600785 828192 474438 429112 50097 404695 370234 851016 204173 507771 549847 702694 722387 123425 878620 752122 571392 605299 132508 605119 454969 283896 880992 309976 718674 263478 367921 524633 991574 617232 608527 53466 302982 357309 399111 176837 22508 534415 646531 337042 351315 979313 819608 311094 113742 477741 628614 744603 669561 283150 323313 740508 857076 803640 877112 438914 247629 797214 349939 508251 391016 587696 402422 612324 885926 988305 319990 436 115776 938864 294019 287079 513691 140558 254822 383678 819001 520935 580922 630656 642527 244822 990328 74753 382892 835072 695756 27312 94630 75086 444376 538380 827187 407332 496795 57934 17848 131959 883009 748333 641799 799…
Output: 159119

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Trader's Ember shelves - MEDIUM Coding Problem | CodeTikki