CT42317

Tailor and the Northern shelves

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Tailor runs the mill at the silver mines of Lodebarrow. Today the books show a list of shelves, 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 <= 2282; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 515 18788204 819055179 482113123 163894285 757965447 62595500 841135184 382192920 91762436 16046835 443493966 400481084 527288122 493066975 986380830 646984981 82195634 377725312 294317726 138835229 166103332 927570825 428571363 131104196 293086523 879037582 577566700 933264390 45937035 825872402 497709549 468585328 458199754 803216595 430536399 154725381 131141515 179425504 679230679 336945409 622573443 844903482 42488570 55704643 447753505 946035191 368453359 95472429 361779392 736258299 71333974 838272410 290238986 102447255 559857316 720287340 673182287 271975359 197225763 319479818 147513625 906482271 299221478 783734777 686808976 489631141 387380479 158678717 510736208 580061466 473727858 415152340 396769712 233770815 270384589 802859221 803522988 234284332 106815290 256157715 373977…
Output: 64551

Example 2:

Input: 2233 2007 572 2044 1095 913 1905 2043 558 897 116 1023 1101 1241 1577 1485 1116 1337 1140 1317 1087 451 973 1582 2065 565 1697 2128 1257 1469 915 1351 1272 1605 381 866 2055 1191 1528 574 1285 342 110 2130 473 429 35 799 1927 1328 625 292 823 721 801 2060 632 879 1953 1721 2140 1212 800 532 471 82 1358 1792 187 205 217 683 312 1027 880 1949 1929 1567 1767 262 87 143 529 2168 230 1397 1117 491 122 1588 690 980 1881 596 7 695 1998 883 1016 551 840 1777 781 1749 744 1182 819 1876 1984 788 978 23 2037 1562 943 700 2056 169 1573 1661 238 1840 1688 1702 929 1050 1320 40 843 1665 861 2217 1231 836 1877 470 1640 948 1340 968 1572 1706 1277 380 2024 936 2091 1482 239 1237 708 712 845 1006 1217 1541 1071 777 325 1195 126 762 234 1600 793 1843 1060 1683 743 99 779 1387 1466 826 543 1353 1310 103 1489…
Output: 1233545

Example 3:

Input: 592 838823607 986568928 205737461 470177349 549205930 84299860 441132907 484257329 601387758 10084586 647599727 295095213 624275671 541907389 956992735 700569544 892863428 102454242 463588281 884882181 810234356 259575109 75889968 320027192 364377360 418385030 818807235 496594914 310469080 95167896 158602406 940467516 222925976 294154769 845966880 947607261 599983081 497964992 601856626 485562 565431296 309908944 509038790 236890857 664579148 997769233 758871253 711538836 195864642 664197943 988316494 4412016 776322581 418254312 119974540 53253746 838442901 800464648 132069778 464779250 860151029 533144924 281405680 510868417 393014171 472580562 300653233 494709232 829021520 30190225 982208079 189602283 743798524 309684037 394884600 959471561 800141716 259849569 6942140 464186312 9076845 2…
Output: 83761

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Tailor and the Northern shelves - MEDIUM Coding Problem | CodeTikki