CT50600

Uma and the Disorder Count

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The council of the dune sea of Caravanrest pays by the answer, and Uma intends to earn it. First: the full register of shelves. 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 <= 2348; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 1423 1300 170 1240 1056 847 1244 59 811 620 453 736 548 214 452 572 874 1059 732 1113 855 1324 43 349 328 854 726 869 966 424 639 252 1165 1286 674 1019 759 123 1090 1396 237 659 406 317 175 493 1378 1026 1075 377 653 922 212 1405 285 1116 357 256 71 642 1035 1047 10 564 429 578 863 980 311 373 28 1265 295 1001 914 702 699 574 450 816 682 1409 1343 1088 1277 1154 238 988 226 261 910 112 705 331 1180 1307 1114 917 752 17 115 398 365 934 139 1303 788 781 251 247 1219 1359 830 496 1170 88 777 20 876 650 835 68 567 1065 9 1391 1189 846 235 1297 144 849 386 292 1184 1 83 882 1008 1415 405 442 1127 444 1092 1304 731 938 909 743 1217 1070 58 142 990 617 502 213 480 821 722 1161 466 1375 138 234 95 559 516 313 994 1038 1022 271 390 579 958 918 1109 1130 877 652 809 133 1420 1014 933 1102 890 896 4…
Output: 499140

Example 2:

Input: 2070 568736609 550750116 300968540 210668223 24189722 556133681 709441853 219581974 768269485 155170743 520518843 27839920 821556300 906001522 790368486 562933748 982573104 864858075 813459480 210300789 531026817 248535801 740399229 480996597 776712752 29569860 418611511 851553080 663908186 693807151 853583052 388129938 257916943 717263008 36986737 849978011 229494984 799945929 793026805 491566229 593338585 541650137 478100837 143790173 122905755 363947014 24494254 997926663 237536348 484742796 827774633 861337035 493622790 526211753 739292858 415561303 962595441 293438990 299623906 638379084 698810 918197341 104716449 227582310 987580640 627059440 202831204 653959988 67297247 947071774 37037015 921098666 425870594 444037021 445187562 191427431 293919720 685541768 109636261 240112584 77282…
Output: 1060965

Example 3:

Input: 2125 870851740 496391525 12915990 849780953 692241581 647009865 755702562 507914542 989581535 888885974 684784191 703478534 918586571 964449747 969863917 960782618 318981378 849546614 150204301 283993808 815215360 781304677 811289412 130346811 106152145 59535396 59378700 195759922 981153457 684742633 99311511 513376988 500565532 991207419 524587403 481327126 989773401 400429419 916564278 371956619 473234433 260497410 985558020 724955325 312875671 59559828 867446493 776582670 371651409 958734737 531544320 835531745 576862181 20961474 98426932 55335030 633504122 408949354 511569841 448771616 95953986 82346777 348147020 164628881 244158730 853193483 348349239 499979614 365783788 56672411 726877767 177679094 573520205 181110039 691802095 5430926 992141555 890202181 259639818 775246737 90292590…
Output: 1131733

Constraints:

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

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