CT63899

The Disorder Count at Crosswater

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Before the gates of the ferry landing of Crosswater close for winter, Piper must finish the registers ledger - one figure at a time. 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 <= 2905; 0 <= a[i],x <= 1000000.

Example 1:

Input: 1616 68995 201454 626089 954339 478718 394668 974612 232506 708691 212639 663291 349274 568960 78812 555195 802842 993947 434134 74537 357996 426826 112118 52041 112259 189335 426326 939432 250223 435088 532191 520062 55638 52539 653795 270447 971026 585130 259944 93691 897386 147201 908450 44853 823808 988340 253341 416141 98471 458138 617242 109917 748851 570207 49168 625674 40136 983926 2 907929 766861 172690 136693 487649 755831 580587 864052 535333 965166 568043 678182 755824 283189 325911 980852 751224 244678 490304 912991 269465 556586 403703 174648 420515 698965 208170 531177 237092 905005 183125 404108 341171 108141 951174 633892 124131 418341 555318 706551 839741 740509 516165 748644 821187 851885 251121 742238 963536 620745 909486 648716 790015 642576 330417 311336 507953 767754…
Output: 657291

Example 2:

Input: 1799 1143 383 791 309 1270 785 57 1592 271 1374 528 1524 152 991 480 1370 1284 1072 569 1473 1112 813 584 832 505 963 1128 721 1792 664 1489 55 294 306 1383 1191 1331 1223 1127 42 511 61 522 1539 424 1024 1551 880 1639 398 1145 98 250 964 1517 992 1025 1166 550 1781 1079 1735 1416 1700 925 1279 332 462 385 889 1148 985 1741 926 1316 492 1740 130 291 1751 701 417 1213 279 373 1532 812 773 503 209 940 1009 1689 1384 92 1790 62 1381 71 930 1785 719 1275 1228 366 953 559 228 1357 389 22 1786 1344 771 1631 1324 657 1168 12 699 1073 578 495 1409 137 1220 947 1552 1059 1527 608 491 730 131 1661 1285 1016 673 157 3 720 1757 667 1382 1478 295 769 1488 268 943 299 959 1796 181 549 819 1563 765 1603 474 824 994 977 1558 441 477 1348 1670 742 1352 34 1411 640 1599 1238 205 554 133 1456 610 668 827 108…
Output: 798054

Example 3:

Input: 950 561 554 766 108 172 284 887 237 115 398 133 435 251 837 544 811 566 381 337 135 18 872 131 399 540 143 225 838 14 504 384 274 824 612 701 478 607 794 510 192 575 252 557 52 124 444 593 326 163 856 352 798 239 634 255 785 873 422 393 43 805 489 303 38 125 902 182 147 613 374 689 642 416 112 102 357 581 458 730 530 664 446 800 590 801 847 240 917 638 777 362 336 745 48 197 772 0 42 390 430 895 31 912 755 588 375 421 79 483 150 860 438 232 763 636 63 94 699 573 231 391 662 499 897 107 123 200 469 731 246 762 851 515 484 647 584 378 262 339 173 89 842 783 207 28 535 310 694 831 411 679 734 752 624 644 297 804 264 757 220 432 848 904 270 869 356 453 700 683 858 572 833 174 73 330 903 769 704 30 37 24 599 500 286 19 179 896 660 145 568 386 120 836 787 445 945 194 656 216 187 72 778 486 748 6…
Output: 223356

Constraints:

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

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