CT41574

Freya's weights Disorder Count

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the mountain city of Highreach, Freya records each weights in a worn leather ledger. The guild wants answers, not guesses. 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 <= 2468; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 2037 1239 1181 1137 979 559 1523 364 582 190 928 1574 918 1706 721 1247 112 315 1603 459 1171 923 224 980 1954 756 109 360 686 297 935 1820 1919 1142 1599 1183 770 646 229 602 1712 896 1025 296 1969 66 829 1236 699 1605 1362 1012 1572 1805 462 1194 729 320 1095 1730 1769 589 338 127 1010 831 622 1584 237 664 157 1914 1661 854 81 654 1675 512 1663 746 380 473 1473 1427 798 1163 1790 588 1670 1751 1630 796 210 1125 446 1482 301 502 1478 77 1092 1810 1848 1556 2032 1800 994 1348 1944 339 519 1377 884 1821 45 1808 685 1261 206 1104 503 1536 382 1185 341 379 1859 709 2002 1074 327 1440 176 1779 213 283 787 388 1739 275 1325 1612 326 637 50 1803 1338 1521 639 1940 1145 1532 1893 1699 357 1268 1107 1538 277 279 1033 374 806 1345 1451 1293 1211 1935 421 1197 1302 627 1750 1474 1567 1839 1315 1400 …
Output: 1009181

Example 2:

Input: 130 599289117 162750950 388875364 304293187 50081978 404630875 579218000 701761987 185342483 353701815 50332468 988239434 546423566 87360627 878872316 179615729 835831851 481428860 348899075 993441204 504551220 689046050 571944261 27977688 830263058 424279378 937354957 901165482 672313654 688923334 365269959 350662520 602419766 947614756 258980553 424128810 472572359 471788708 369203030 56115069 164331216 135389538 211492183 376893045 934848206 611773004 799365075 829304516 786584643 299262286 367968071 670171507 855360720 499853234 267034770 785275172 576653889 767456319 613478757 360832387 151281994 332167471 924209966 50980774 546308021 448241203 46867162 988742791 660393677 485267712 89711646 775557073 935114312 517531284 238099988 666952034 680920500 1124628 361848626 360391421 488846…
Output: 4134

Example 3:

Input: 401 153 147 359 82 220 51 202 277 63 81 239 64 291 243 128 21 370 320 172 9 215 307 283 203 263 289 58 180 195 134 343 132 133 19 379 75 377 68 45 95 6 50 318 276 364 262 226 86 358 135 11 146 308 183 314 380 237 3 5 97 302 341 161 176 148 122 309 67 355 65 154 14 397 345 113 396 20 1 354 287 88 15 200 120 382 170 87 152 357 69 182 197 296 272 248 271 211 242 201 228 374 212 193 300 118 236 372 330 371 96 164 198 46 306 40 175 144 93 319 394 159 297 378 139 4 57 387 92 174 386 375 329 298 185 8 292 100 350 266 26 385 254 398 188 157 76 344 219 268 91 393 249 384 261 80 257 281 216 171 156 316 77 207 233 32 109 155 235 223 213 324 121 361 181 224 29 73 66 227 126 178 167 267 162 278 115 78 124 288 229 83 265 294 60 356 383 56 312 103 255 347 12 110 131 273 179 72 279 194 368 102 391 274 166…
Output: 40584

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Freya's weights Disorder Count - MEDIUM Coding Problem | CodeTikki