CT60777

Fletcher Counts the shelves

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

In the trading post of Goldmeadow, Fletcher the registry keeper keeps careful count of the shelves. Prepare the winter inventory, every figure matters. 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 <= 3177; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 2098 884082477 372880825 963551300 967687846 418435922 435024239 585140947 112193457 517065116 967298720 318265308 42889510 908150592 651210323 149909732 265830213 494725561 899292951 777240692 424541603 471986304 496952241 558250848 430369659 216077589 822845127 628345573 587734537 697028291 51482398 788637697 812300881 411805583 393506875 648312126 560731946 894840885 119217481 812017260 747411631 526861070 365789566 477208947 660473283 248117960 96332106 19749279 777354035 354878807 200250765 562265339 974121313 741865708 63810733 158657703 820586220 975608093 183422831 449134576 393513381 41473503 730710645 745574730 154930493 54940730 878214439 542977838 700741190 845951934 482520585 200709619 260266518 78020863 292199760 648016402 311584275 536294159 101635248 871524886 56845593 2604…
Output: 1113562

Example 2:

Input: 2510 723690255 671586018 719019198 663911069 685596505 606377954 953584087 250544880 291398760 675223293 967516896 547688014 313079583 189957750 526060112 873495612 164182721 522926765 654312291 273271618 809960211 5710093 432853916 729253971 134360455 631220471 163822504 196405028 766166931 696896851 721360390 667645099 631885327 971942322 14359697 145008036 343268272 598619510 596485423 160550509 395598514 933668472 328469668 758308203 724054222 456753342 39103756 33467313 666993103 250225475 939899675 147160928 716509043 812745722 617382925 440972962 81326554 160791839 839348185 312073975 774392884 804496242 580107288 337411758 897141574 753724496 604147589 384506927 511057975 785427306 353087077 467645531 442149976 476805890 983882187 185017760 748958222 444286034 151440201 249347534 4…
Output: 1565576

Example 3:

Input: 1791 902 846 496 426 1294 488 565 643 900 1407 504 699 179 381 1575 206 264 1388 622 110 494 560 71 328 66 22 1783 194 18 870 31 1183 1692 1436 1613 354 1498 1442 303 1214 295 229 1773 1045 430 1312 1184 1434 1281 845 1066 670 718 899 1140 618 269 154 1031 1080 491 1600 881 165 356 865 214 192 831 23 604 811 616 1216 1690 544 1753 1489 583 742 930 440 941 1177 918 524 849 1450 1762 731 1423 567 43 744 187 1059 1747 237 764 248 1386 161 94 396 613 987 1139 593 1563 119 477 1191 1430 98 456 1269 489 455 1353 481 49 720 657 1651 1646 576 1241 1053 860 102 162 1090 1481 80 1702 186 1344 271 1707 1017 1192 1542 415 1524 211 1262 1282 1287 640 631 358 636 1245 722 1471 1186 997 529 1656 1618 1114 1368 1207 1490 1644 915 1160 129 1298 706 1411 634 1185 1766 1296 1382 1215 54 300 1170 218 213 1550…
Output: 787939

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Fletcher Counts the shelves - MEDIUM Coding Problem | CodeTikki