CT58868

Felix and the Honeyed registers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Deep in the basalt cliffs of Obsidian Shore, Felix studies rows of registers entries. One clean number will settle the guild's oldest argument. 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 <= 2829; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 357 194 245 265 4 23 153 93 10 277 178 213 189 286 209 162 52 96 88 232 83 27 208 305 302 172 353 43 145 59 171 156 321 221 113 177 140 217 207 103 56 41 48 285 228 253 260 79 98 316 314 303 169 197 290 236 216 154 117 345 279 80 201 222 190 199 28 159 19 342 291 301 293 338 40 346 36 13 78 137 85 9 275 229 319 72 269 21 120 326 17 24 298 315 287 312 332 62 288 146 200 181 69 244 280 299 66 14 225 33 344 255 188 87 158 12 241 94 219 101 152 75 306 351 7 309 143 125 123 248 348 147 122 184 330 116 74 238 149 161 53 168 294 89 334 47 20 157 42 128 44 151 261 134 18 15 297 45 247 284 92 206 138 38 272 347 249 102 170 165 331 8 91 185 340 320 35 349 167 148 82 270 233 198 104 187 254 220 46 49 237 323 121 202 129 34 179 292 11 273 250 212 324 139 329 133 341 317 268 203 115 174 283 204 227 180…
Output: 31291

Example 2:

Input: 2231 1083 1858 656 1082 559 1484 165 1272 2022 1586 1685 278 1273 708 792 1810 258 1240 506 1202 2050 839 902 1256 446 2191 1305 1469 864 1357 328 2164 919 1923 32 3 657 1039 1006 1104 281 873 1931 1183 1299 186 1363 102 706 148 2187 536 1341 1225 588 985 2203 564 351 726 2138 1365 689 1962 1988 897 1491 2108 1963 2064 21 391 1900 1136 1540 580 130 1438 99 2008 1318 1346 1015 2174 1532 1842 556 221 1736 1377 1428 1874 378 1709 894 1605 245 664 1681 2121 991 2091 859 2184 1667 1571 1227 373 1298 2222 1905 437 1636 1314 63 1310 333 625 1607 892 1723 796 1269 785 1818 889 717 1512 1690 117 1757 511 1107 252 1324 1304 363 203 2043 715 942 2065 1474 530 1965 755 187 18 1568 1612 1663 1939 457 2186 2206 979 347 1894 1250 1195 1890 2211 1887 534 736 1001 1323 1286 911 1220 973 602 1348 1683 773 8…
Output: 1272301

Example 3:

Input: 688 467 20 633 513 171 86 588 214 613 219 637 315 220 270 37 336 625 276 570 652 7 244 600 333 124 583 157 471 187 592 681 163 365 446 375 537 23 602 514 667 81 13 499 369 291 550 182 524 28 395 183 476 666 195 410 461 680 554 634 582 669 313 241 116 248 517 562 445 523 243 317 165 632 96 480 363 256 259 586 48 651 624 252 188 673 321 307 397 269 567 123 126 114 191 416 4 127 459 133 686 160 351 389 84 137 18 359 101 630 168 565 148 684 142 320 283 424 249 50 185 409 265 103 429 164 258 267 515 200 9 70 465 119 549 318 309 92 102 63 112 97 44 95 346 390 67 225 173 450 17 358 158 388 498 420 25 662 12 254 347 75 231 55 535 36 451 52 73 687 538 253 280 325 642 430 656 660 236 464 557 89 436 91 396 162 56 479 473 501 335 345 508 247 166 563 177 556 370 591 372 658 68 108 512 27 678 454 100 71…
Output: 115493

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Felix and the Honeyed registers - MEDIUM Coding Problem | CodeTikki