CT49433

Chavi's Disorder Count Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Chavi runs the observatory at the honey farms of Buzzwell. Today the books show a list of registers, and the numbers must be worked out before sundown. 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 <= 3512; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 2223 189436307 152813065 567980619 72667030 498595243 514569683 323621171 719013324 927698748 267664852 968885669 977202474 804409610 970160359 446668946 32339671 178851410 391999998 92618580 405846711 531221571 761434380 777420121 644527782 752471341 944140126 381349003 508863392 238068020 761374070 758364868 689340671 281018726 680273394 56422467 544586250 208259727 61085501 809829290 434533092 365404377 718447092 88582921 888421933 635845383 400586523 284626334 497831917 318049885 350382718 547594046 403940249 648540706 445860469 700303028 36561909 138363612 912239946 836650347 438811271 321292094 9404113 599976266 805132672 429606015 51824567 520836875 293694828 503789 465628205 613419881 67697996 245449898 356383275 669534421 894588045 473156113 388324221 633641351 338456584 385237107…
Output: 1224639

Example 2:

Input: 525 293219789 45162931 445641814 940345659 165144276 709799588 202802894 461617229 130168478 910083661 100618735 162158870 741785392 325842450 169408911 483779648 632001644 813034129 635346145 742593683 201717699 455131850 73748 223664420 388246219 997722662 625677288 715851513 857548428 82014726 971839253 909094878 459613830 97935608 601374463 673001918 638868169 113583412 663621084 395802370 163330561 257218754 492504051 976365970 790401530 132268542 396525912 679775390 425651115 828665487 620955642 973215273 653484119 278689834 846646507 780584865 234106180 493486832 270535689 388250749 403100137 121728720 400885686 201259999 356274657 160521564 910731869 348517418 491505274 482937048 736855686 964741071 222507932 626640653 759787430 738549212 783642652 84263824 362193989 582965107 3424…
Output: 67738

Example 3:

Input: 1237 792 167 814 782 930 1001 961 673 365 1000 1068 1118 228 196 132 697 979 973 424 376 503 50 620 194 912 832 366 569 131 1099 174 677 316 17 21 453 498 866 332 135 352 1159 257 355 1011 790 440 401 1158 29 284 956 686 1139 464 40 649 1145 767 385 668 339 542 318 13 665 931 904 1093 12 264 864 6 313 1140 802 1112 1009 959 650 308 625 559 899 957 391 384 382 252 607 303 478 102 717 1134 1006 1186 801 734 710 8 504 1129 343 14 911 582 944 1071 116 200 797 903 1180 584 1172 524 400 104 696 962 595 23 913 232 143 624 1079 977 727 991 937 405 694 150 597 4 1155 42 705 1072 591 1204 746 670 791 932 177 982 1039 90 341 879 614 1197 519 1190 364 849 298 445 89 1224 854 280 726 105 902 388 848 1188 454 334 459 348 1231 467 103 54 155 867 114 530 719 900 540 461 578 1086 191 92 395 468 1220 984 13…
Output: 374577

Constraints:

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

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