CT41721

Jasper crates Disorder Count

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Hema the cartographer watches over the ferry landing of Crosswater's stores of crates. A careful computation stands between order and chaos. 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 <= 1907; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 975 474 501 807 687 51 527 609 735 25 262 71 45 736 120 313 776 82 347 905 902 840 619 448 920 231 939 702 413 332 579 515 368 921 265 908 630 478 230 715 10 703 284 404 781 37 178 891 656 799 243 635 594 184 525 769 270 738 317 183 573 493 682 790 863 636 42 957 434 464 772 360 408 780 752 316 279 533 649 694 483 940 933 556 150 831 201 198 958 383 234 49 149 299 440 357 856 26 405 716 133 542 174 336 659 54 342 138 519 730 179 123 247 200 578 701 621 909 521 8 393 370 626 623 304 732 849 591 647 777 585 913 725 415 387 526 612 508 548 681 249 798 340 271 80 400 78 52 914 912 727 479 277 208 604 485 90 837 879 134 367 337 346 455 534 190 642 793 586 471 753 743 942 224 126 188 255 827 963 358 180 651 286 759 644 930 628 667 516 927 860 658 385 530 567 468 570 744 69 105 796 229 480 83 257…
Output: 235593

Example 2:

Input: 165 848552 981975 -269580 417244 -794370 619640 -715919 -747813 -686832 996809 -508308 782290 -374149 -321449 -596031 -271488 726718 83516 -392224 316645 244075 -801508 66904 445931 244039 297739 -742501 851855 -787947 303358 172178 927397 906090 983106 134858 287294 -563589 183406 963350 177523 960311 -630466 -931536 -77065 934089 -764835 364533 58372 129084 -429362 -568894 -47521 702439 626901 -563094 -944010 996488 465023 616222 -768231 -352001 -686741 -507429 -43407 645675 594743 383343 136980 303079 -506659 51742 -30052 -626265 762104 -436995 -51184 -972746 -474715 793434 -324595 622498 -874694 -381474 -427646 849402 -695917 -567928 354146 -960955 -654870 499638 -517321 -689428 -487389 373288 227618 935870 -620618 -553194 816099 -271092 -698067 -54627 310504 -83105 999200 421304 23102…
Output: 6847

Example 3:

Input: 1680 967730 23445 -727793 -763857 664934 91090 -475990 -481696 -178806 950694 -462346 249918 -701934 685872 124437 -13201 822921 -597268 162311 156363 333356 -409433 947616 863239 704854 -784636 -457180 897 -292496 673746 -186075 -243891 77127 -363155 -786394 -973455 801454 -180963 903984 264794 -53011 809519 -874700 104340 953219 -819579 -393924 -339991 337992 547772 939379 -695845 -410519 -503483 -784179 894052 -286508 -291478 225952 -658220 431286 -754212 -457272 -860827 -817325 380888 95269 -735786 772116 737196 541005 404849 173262 -966699 -477404 446724 586989 932487 -408329 241655 -747344 930692 822173 603398 858240 965444 774832 -34374 225197 -362955 815456 -418779 -289883 668331 205128 -786986 -123477 849659 -560838 273909 -807575 -157005 842892 -127985 430804 -603754 -401190 -197…
Output: 706363

Constraints:

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

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