CT45766

Librarian and the Disorder Count

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Deep in the marble forum of Argentium, Librarian studies rows of crates entries. One clean number will settle the guild's oldest argument. 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 <= 3070; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 1777 392313069 692049644 894234524 777287505 478693031 727444762 521365321 890623929 671868016 300154918 14913755 52618949 533922009 40399376 292559766 623799714 574157862 105638448 149806639 212598260 368934788 34005122 41613810 561034049 219581251 257944963 901798073 797563033 727823597 484530766 124138224 550743726 425951019 290648148 118221572 688666973 953236158 476490412 696810030 87377501 211835116 905351231 437823299 978284564 5944876 860624475 169119857 584530465 343477017 845574477 425016401 954370091 335204538 291693165 276304004 94583760 50711816 634534142 72314864 987640411 438339227 408680444 685420374 723579873 980166886 924574694 822591742 476888471 528343348 808163894 917945991 224099467 217426566 444234007 236482005 740941741 882029912 722402181 712191062 149630329 888343…
Output: 778280

Example 2:

Input: 600 615277707 96236357 686009059 733296104 356042093 596085089 312700897 528334166 231305684 953285775 51377719 580361749 35126928 878618164 641462658 399538353 390960014 153468086 770093673 219129573 758310229 139730481 493675733 418542863 193373296 696171536 917522092 895093821 461199885 622643292 37618434 776419435 503344221 454639076 842814788 756320905 184278651 918896708 411366397 508992253 651420125 268655913 49015914 499492755 298127391 210706861 85523517 820112152 375034176 15256562 114240841 644811054 424346996 722032845 108601769 34241598 107986585 315626604 817180406 463686710 628283158 108077257 69727345 845401898 206577831 22632916 957841412 298806271 54398432 963362543 765719838 912518306 699905141 503035055 860654016 735832794 617562070 451184471 994604385 341657183 8438996…
Output: 86072

Example 3:

Input: 2892 273 2213 915 1731 1207 366 419 356 227 1962 1012 551 1148 1393 39 1469 2467 2825 1050 2255 2481 2221 2837 2407 1844 1436 1929 955 1840 1936 1897 1068 2122 1492 2692 2882 1394 2247 81 2782 2543 534 2264 2607 923 2037 212 454 129 1459 2885 362 1663 1122 1590 2394 1992 832 2864 584 981 1869 119 2599 2294 2776 1200 2773 774 2730 2272 90 721 1034 2592 182 1752 847 2836 2374 2205 1893 2276 2484 1611 1407 1846 985 217 2497 48 2794 2662 1419 1323 139 1682 2868 1374 1655 760 1951 2108 2666 292 2418 2513 700 1994 2849 1285 1738 1132 873 1679 723 1479 1333 1135 1449 1715 1782 1001 2014 741 1896 2370 714 2163 651 2689 311 136 1558 2004 796 1326 922 1622 1540 2709 100 2827 1979 61 666 412 2039 333 2857 1448 726 35 690 638 2049 682 563 893 947 1363 1000 414 2169 784 1277 2133 667 2508 2528 95 2082 …
Output: 2082976

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Librarian and the Disorder Count - MEDIUM Coding Problem | CodeTikki