CT41953

Nico's Disorder Count Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the seal rocks of Barking Cove close for winter, Nico must finish the crates ledger - one figure at a time. 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 <= 3237; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 1735 790802546 839301854 873727751 327558961 760707093 791610923 401617825 794469055 386462947 806871610 61419941 494453143 965332583 249697140 172061558 764010000 955563301 974828461 85991279 270722242 291751929 779651111 726206916 795717510 744433749 187859434 815595944 287785980 358035672 289503474 516715474 730218527 730952944 760617636 2149275 296707792 432250521 740000417 932541916 640174880 581127349 53595874 448094090 515584943 429451085 205769137 831663278 220882522 320936909 914219457 73864867 915673023 731253986 623940111 765470039 664035045 570650218 993701323 777571431 522186501 634343076 717910545 657369565 503312918 836846620 476090481 352633234 441887331 547248671 46636259 960198833 455090911 83235094 378975703 47325419 29196805 734753918 603070442 682359966 606007052 52359…
Output: 778141

Example 2:

Input: 2809 2466 28 840 1195 1608 1351 2426 2657 2676 1115 1284 1840 2649 2435 777 177 1104 136 1616 1789 2019 2684 2687 137 445 1892 1716 715 620 677 157 1706 1656 670 97 2286 983 899 2021 1092 744 281 253 615 2504 1063 122 1398 1235 862 101 1753 651 604 613 168 997 2414 1655 1442 1967 1196 2404 23 1683 2515 2452 1909 1177 2037 668 2434 2681 407 905 2491 633 2316 389 2204 2326 842 1948 821 2102 1687 2066 667 1255 400 2203 1788 2476 656 2374 431 2766 818 1651 1944 2225 1254 1215 481 1632 2614 2517 2376 1287 685 1023 1399 804 2620 616 2287 1047 593 265 1819 1974 2068 1342 2740 1961 2527 1942 2446 1866 85 2565 238 1824 2694 647 1271 743 330 635 1573 1036 2769 1585 1846 2405 2718 1337 1437 1460 570 2222 2473 373 2733 436 185 1267 1356 869 1152 2165 335 871 2610 30 1149 279 1875 819 2141 187 1722 133…
Output: 1949998

Example 3:

Input: 313 571979759 183393193 10015249 475847274 691452900 945720623 868187127 940115681 452668326 229691726 52722578 470893416 719397906 221206576 406912573 129630813 440540042 925151964 815427222 477191112 193517301 357654290 513864738 637572019 918979949 963272723 881975088 254427311 36983941 643332348 879952669 399714552 139497338 700525714 352211972 46988405 998602047 353518741 848451822 641003299 558210789 440630792 221654698 630903357 418874155 928549982 199696373 42724959 254021966 144508300 707660068 359311663 460167515 798659789 944922111 852475925 933206528 154745080 304854463 941456312 108038346 815134372 222156085 193810300 628533670 445237309 324184724 186786918 247691459 15731128 413454139 307134143 647522103 89111281 753986515 671279711 691429804 332370259 260305688 979632712 387…
Output: 25949

Constraints:

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

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