CT61861

Xanthe's crates Reckoning

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Xanthe runs the timber yard at the island market of Coralcove. Today the books show a list of crates, 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 <= 3470; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 2604 657286823 177004665 304223845 672191534 45911165 524702742 611662190 117087579 910324589 952716044 832571222 271090183 998342054 275156528 56834839 631584233 981447622 643046646 200930247 585713023 720696464 626484210 756413657 720878142 753470445 65926319 450417016 962093319 926623988 793670271 55560650 267523361 180863193 991116159 143019754 269435948 80517880 333906163 878752010 797206515 218385398 196939355 951982075 202974524 113141350 92432396 797389416 402841191 544806257 284241218 953505449 549230293 683977017 207006460 260071707 797688023 336614339 420436507 498126452 338026845 62781329 122083655 20200915 110221717 97331640 340788181 188124480 708185050 388735506 419594004 674603473 437792286 139336802 149503049 906261818 183542327 859748484 102779539 325774342 242631557 3951…
Output: 1682616

Example 2:

Input: 1084 944154149 248581381 741813098 328387736 409599616 581318461 195389762 485199034 770695055 587197829 818891417 791519318 226612749 455745981 120217604 989145642 205922703 369925447 829791107 239398711 280564865 715914961 99987234 908180797 768554105 96038519 109176853 729885889 726512060 722064249 348330239 679228991 615428198 516941686 277618681 149808828 257459470 769108605 890055397 247180915 457805952 436809741 998349261 116501981 862190222 366048811 562500518 955914052 965256467 482712727 313019660 793146376 637961992 237063151 158212564 479279167 559166593 919709165 275525679 688927234 291532597 722364493 393433553 243072441 417604521 279090562 768050800 244396033 701547086 530261457 708837931 609324885 689241177 267302961 456633032 978478813 272759964 853945828 538945327 7497963…
Output: 292598

Example 3:

Input: 3222 2962 2240 961 3217 14 905 2411 364 408 662 2894 1447 2304 874 2043 2538 184 1541 2129 409 942 884 1403 2916 3042 3160 988 1346 3077 3113 2183 1394 82 1658 242 982 1140 1449 2518 1812 2212 207 529 231 572 2543 3206 775 233 1190 888 386 1960 805 2797 3085 1653 690 900 438 1258 605 504 2834 420 1753 411 2575 3021 1457 1692 1064 1158 1451 1867 2137 2948 1003 827 1907 2909 1095 3142 689 2897 1128 1063 404 2294 1289 1967 2143 2690 2632 996 2610 235 2464 3068 73 3066 1524 1395 667 2489 1572 2695 1922 2885 728 2046 481 525 3149 1225 1284 2119 406 1886 2151 77 298 2422 1887 1079 1746 609 688 2524 1053 2450 309 2585 3010 1038 2153 173 2127 1126 11 3179 493 2279 3195 3150 249 1964 287 1532 1512 2769 533 1808 676 516 670 1144 2775 2498 2523 2495 848 762 2550 1056 771 201 2850 2150 1379 2155 2591 …
Output: 2563179

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Xanthe's crates Reckoning - MEDIUM Coding Problem | CodeTikki