CT42499

Iker's Disorder Count Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the tulip beds of Bloomhaven with crates of shelves, and Iker the dispatch writer must account for every last one. 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 <= 1710; 0 <= a[i],x <= 1000000.

Example 1:

Input: 678 333 83 310 401 626 245 277 0 380 307 670 408 671 667 95 105 16 591 489 571 12 6 634 659 285 498 509 426 599 136 46 436 125 464 435 236 167 288 465 359 70 63 502 554 336 116 395 495 547 337 410 389 340 159 251 490 303 556 164 10 255 522 67 44 617 273 420 636 439 205 329 656 239 574 124 427 85 155 505 191 623 646 520 317 101 290 265 364 421 129 521 194 654 431 325 555 143 60 545 665 306 462 512 343 30 151 59 193 481 647 122 121 104 491 141 269 374 524 178 496 541 11 221 653 582 561 244 549 371 112 93 332 638 402 386 366 614 42 567 672 213 511 399 9 385 52 316 84 113 254 575 65 64 560 479 438 361 473 287 261 480 442 345 537 160 484 109 249 532 627 610 651 368 527 312 434 631 207 581 604 34 156 510 452 383 517 611 92 652 411 514 419 538 281 75 192 40 33 157 66 247 377 413 246 450 339 600 3…
Output: 116810

Example 2:

Input: 1664 598 176 1013 479 226 546 990 570 883 1395 192 954 225 1348 1596 191 877 797 830 388 810 545 456 1396 119 346 1315 1545 1046 1448 1636 1150 807 1097 1504 1561 1544 310 899 1259 1615 1597 865 596 1318 1029 279 1000 1604 1072 1278 126 941 553 197 1087 684 629 681 1230 537 221 699 155 1659 528 675 1184 1111 1212 1478 615 274 413 386 982 901 397 1131 1068 224 1647 58 238 73 1549 1186 471 1078 964 527 422 1174 139 263 969 536 69 914 1002 215 1497 908 89 1350 1311 1484 152 845 738 989 1232 1515 772 1638 1646 231 780 146 1471 795 1138 539 549 353 1624 863 897 1492 229 1253 1594 277 1297 1649 789 307 1282 1532 1213 1467 1203 713 656 630 977 746 1206 1508 1374 311 932 1264 930 742 755 1288 319 271 1328 1048 1049 1457 888 1194 1148 1635 1214 592 1058 487 1433 886 368 1586 304 1623 1542 1330 1408…
Output: 703274

Example 3:

Input: 1524 394 957 402 846 9 160 1149 1021 229 890 929 183 595 377 963 1482 1404 847 1089 1111 872 1438 272 1134 185 1436 1145 1289 293 180 1009 1430 1097 758 280 240 447 1520 1425 319 1214 549 921 915 231 60 646 493 648 1178 1012 1164 1368 1151 953 1 192 734 164 835 423 1410 543 327 876 800 1099 720 134 439 1011 0 1447 891 349 100 266 421 966 132 1358 930 1230 1471 1495 391 950 195 1271 106 116 1170 1323 294 750 589 794 788 128 360 540 647 1190 188 1297 526 105 471 740 900 988 675 1028 1054 186 709 920 534 275 1154 559 961 708 32 488 1038 705 546 537 1515 1138 110 613 137 39 1460 250 951 1298 1072 415 1472 216 1222 1334 801 827 1096 770 490 366 1325 1491 826 976 1337 478 1423 1059 1285 1218 351 989 238 868 1496 1320 382 89 355 865 1167 290 1177 152 1462 1426 724 852 668 1128 1440 768 948 1424 5…
Output: 572670

Constraints:

1 <= n <= 1710; 0 <= a[i],x <= 1000000.

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