CT61536

Bright vials Disorder Count

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The bookkeeper Tara has been asked to rank apprentices for the new term. On the desk lies a long table of vials readings. 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 <= 3945; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 2758 -61462 998612 -151326 724277 -510712 -85040 -614168 994289 146436 24687 -351721 735856 248061 906403 400202 -801393 -438798 292881 -883227 -368831 -148724 -753362 57834 -51195 -738225 -809815 -520780 446149 146116 -105971 -332875 365017 927235 118858 199175 -253585 -492868 -54195 -969983 751670 241798 433925 645405 374072 -375929 672000 896383 -355767 -297664 708329 -511992 -605332 737708 -166150 99073 -547474 664885 494894 -126635 -584528 -543777 -625696 -833832 943845 -399119 208213 204271 165419 -62625 80975 -662188 -969759 -458154 -718443 -440050 -213279 -476339 -357106 -563545 -218892 -934938 -283732 234543 855930 924819 774089 749352 690004 -573915 -727063 856668 799728 -859808 886343 -635883 -874715 800037 734263 805048 915573 464536 302926 372646 -672397 -98464 110538 -934080 …
Output: 1919268

Example 2:

Input: 3171 410416 -444227 -210655 455824 -495554 -388291 -923672 639907 381619 -786733 -890953 -563446 -303657 -930014 589616 14735 -720728 109593 40736 558572 767796 62635 729111 -77374 692386 886957 584581 -214014 -957994 676739 -676767 -86312 -847211 -635689 -709807 -940351 986726 -895664 -217542 966891 223961 -892297 -251509 -322030 414828 -98806 344519 -747169 801426 265782 231104 744378 -76300 -925240 415002 -772357 787768 627695 -767350 361379 -187439 147690 942133 -531872 770119 409614 -622178 -118086 799510 898469 694448 563208 593529 -523265 842540 819109 -996833 -899416 649099 -543014 963582 -452737 349725 14601 664522 -241249 -609993 -739467 832513 -484939 -899621 294857 652763 -659825 -293914 -641722 -260755 219215 -605342 371855 -678072 404742 704284 -155656 -173494 550635 531519 5…
Output: 2540276

Example 3:

Input: 2230 1003 1854 1641 216 430 2113 471 460 815 1242 1901 602 2229 1690 862 1631 892 1621 2174 1875 416 823 727 2104 361 339 1132 26 1953 733 554 48 1877 955 1263 1035 1515 1819 1228 372 256 2035 1037 1426 737 719 1465 2166 1260 2042 2192 21 1454 1322 1990 72 362 838 717 2180 1614 1208 588 1668 1026 2156 2062 4 1589 1983 1942 1399 1776 170 1020 1211 2178 2061 601 371 1952 696 641 37 1312 1804 1701 1970 1871 1351 577 384 400 1522 398 409 2223 1620 661 333 1032 2185 724 1070 229 631 861 266 239 1531 213 61 1941 840 1887 762 1414 923 231 2064 1374 857 779 835 1396 1679 108 2210 59 856 385 1495 731 498 1452 1717 1448 1630 1791 510 710 2179 849 654 880 1235 1319 2119 1356 1566 722 1175 1480 1598 411 1576 434 2187 801 1543 1592 963 627 1066 2211 482 1853 1918 274 1360 245 906 1364 2085 1606 558 347…
Output: 1217126

Constraints:

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

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