CT54464

The registers Disorder Count Puzzle

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The harbor bell rings at the indigo vats of Bluehollow; Cartwright weighs the day's registers manifests and starts the calculations. 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 <= 3385; 0 <= a[i],x <= 1000000.

Example 1:

Input: 1310 106847 906735 910381 374489 900241 145404 56997 668509 123568 450704 583724 9640 224867 561868 165462 239949 564344 122710 953221 956385 955888 398722 476167 382135 942695 336322 857177 2103 596875 396918 2198 345350 874851 627741 669055 623419 178468 523197 675971 151027 58655 990968 206585 261811 311394 706916 984259 948923 584654 634421 488555 974923 978624 668461 960031 268350 118829 137862 362332 236598 83298 851162 990854 9232 27705 787035 264078 245839 592358 969735 390566 555720 178197 208232 887510 896469 578527 119946 210366 369510 76006 52805 630991 12395 471474 336397 95813 328048 859161 313466 210234 628755 163461 972129 273628 845868 286261 126670 391382 313732 81605 318660 543827 728642 551681 679408 675038 889965 724403 918825 31357 810850 494406 483939 52488 431436 76…
Output: 419673

Example 2:

Input: 1599 28 158 1530 1508 379 494 1301 281 857 202 55 1509 1210 165 577 1142 585 467 2 18 710 1577 1198 966 850 1143 481 541 254 307 128 977 351 987 1005 645 1377 340 1465 1498 187 801 949 705 1371 1186 842 855 1204 900 1446 350 393 972 588 446 380 62 529 1173 1265 478 923 1358 276 683 185 632 546 1375 1378 1366 1488 14 94 289 932 1490 636 418 473 1590 874 1206 476 734 1211 952 1078 1389 326 1303 245 685 570 242 600 910 941 87 1575 643 1369 1436 1497 1467 1592 988 1426 557 723 549 381 127 286 1126 99 739 785 595 1402 497 1060 1224 498 831 1151 208 200 412 1009 389 116 678 644 770 1479 375 1451 267 997 53 750 142 609 1139 455 699 1306 1019 189 1330 677 400 773 1162 1196 1412 582 311 149 1398 273 905 89 1022 156 1239 1294 1007 1489 1410 7 475 948 885 587 174 1230 774 769 1106 342 572 1491 201 10…
Output: 634807

Example 3:

Input: 3328 733526 617331 278086 413711 285971 769020 935788 374229 890022 65330 758820 829397 126225 483417 356175 245887 316676 786383 932316 39634 299407 184994 626032 699396 483286 673210 277755 475739 257963 321161 27477 470363 444155 474721 104427 978414 763410 766203 67676 900414 198241 704054 197036 682340 688121 904409 676265 155826 916707 483700 26761 304160 42077 211949 735300 211789 74520 188429 367348 868073 678309 907295 543903 866435 194676 812775 151826 602997 991391 670602 511338 295892 950751 735031 33317 710473 339857 853367 427014 170897 508678 143340 944943 805342 814481 190953 47207 141323 234502 632076 420747 690088 147707 193468 557732 563071 450004 809409 344435 785841 916533 59470 913564 390774 795221 425450 891477 763001 824205 299919 498102 667122 970417 685728 688698 …
Output: 2775211

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The registers Disorder Count Puzzle - MEDIUM Coding Problem | CodeTikki