CT62757

Faye's Opal registers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

It is audit day at the herring shoals of Silverfin. Faye spreads the registers records across the table and picks up a sharp pencil. 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 <= 3575; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 2727 2458 569 2603 120 2390 1640 741 1367 880 1304 765 1347 2114 2221 1413 1108 2053 1716 28 1922 2558 1319 1891 1949 7 2551 930 2077 2405 844 1847 2636 1295 164 2502 2533 147 1122 1740 2244 1159 251 2415 1851 1717 1224 537 1046 1668 1107 37 1547 1867 2648 947 433 1409 1584 800 728 1049 1824 1628 2024 2278 1273 1128 2646 1361 1003 1712 819 507 738 2388 2276 1921 1000 1624 2671 1376 24 598 1554 2093 871 760 195 328 1239 2189 787 704 1317 2140 1594 2285 1275 1464 1247 274 1593 1251 2662 2330 1647 1018 1691 973 438 294 584 1575 1769 2489 2049 40 1972 763 2128 2487 1019 2027 211 2026 2438 837 2349 1161 1138 308 1036 1954 1889 272 1080 1279 503 641 2117 859 2420 1499 261 1977 1627 478 1291 2564 915 1185 2594 1383 1087 2547 554 2685 2185 205 1764 1112 2145 1561 1035 1576 933 604 136 2610 775 150…
Output: 1869158

Example 2:

Input: 2546 898931325 67822913 678956798 488224207 42225136 351287009 393060243 137572325 130292073 529142292 489986922 959824277 458044375 155679231 305425079 252708782 152026935 407496874 826650966 913681796 373486978 89432399 57468257 462397221 959797672 18340122 66669734 29636842 295037638 557512098 941093792 981583330 617813582 393281662 995721157 663589600 184497287 582986120 292679584 492715079 723894679 943151463 789327276 996461900 885029932 119122211 799400231 651036010 944575295 262748176 446938174 884125282 54046478 978288586 431131616 925691324 772594695 882088735 185547615 371007739 498038321 128810782 999731316 988316214 928455271 505630257 201516206 633986984 12337182 361662640 428978700 491247811 177939427 149361848 586592280 700231003 981172799 910305220 105538756 543330126 3596…
Output: 1627659

Example 3:

Input: 3542 709710297 577132514 585523781 668967759 506234529 509561358 595477442 817479705 913102622 173645999 802965869 325041853 428307005 489675476 462564323 193376974 143918483 763397852 397445431 835971723 968072747 320161766 538177396 778586344 84220750 462667974 259153151 968946995 930245229 915196796 475885887 466353801 622307328 458508044 969914261 577043990 919249341 943192372 83294153 811296792 579485395 87608594 233273423 195849779 435669043 518454496 605504866 936434175 378370728 924291247 466876440 701026557 580581838 215645783 581440473 743701631 164850802 617975399 552117785 280283631 35101701 644975470 564622796 170881700 116771921 233579302 95244639 578832982 669356034 882816795 427092935 642530519 466488131 537513139 649185201 363906118 881816558 914839880 427239140 516916093 …
Output: 3188610

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Faye's Opal registers - MEDIUM Coding Problem | CodeTikki