CT64674

The Ashen ledgers of Zara

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the steppe camp of Horselord Plains, Zara records each ledgers 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 <= 2422; 0 <= a[i],x <= 1000000.

Example 1:

Input: 2080 430290 705330 667290 330703 713094 553799 80757 348403 790471 296243 488028 9806 688258 118105 574720 184399 293696 357224 600721 398292 710146 287681 268784 986456 822429 805188 884684 623480 684275 6093 283578 7954 216743 228264 889309 695305 557160 533637 741727 114096 738624 316608 527292 904063 363729 717186 261629 169673 835706 929176 598932 954065 574049 607218 442191 387715 467721 539369 771997 524593 370163 379198 993538 427410 448089 891045 277708 391086 156792 303796 378916 732933 886641 31309 671358 505715 538639 640542 645007 362955 409132 470442 510398 817236 305255 1402 226372 355370 670173 963202 923946 305208 245509 235870 146964 987379 31213 48177 449218 536935 617825 410801 10684 947960 723965 518450 104762 670138 316991 69808 680487 124430 146672 808967 395832 6087…
Output: 1087501

Example 2:

Input: 1271 393 1218 56 83 422 1168 686 940 748 365 549 951 197 581 916 298 217 816 765 415 97 40 1148 1240 837 634 778 1226 539 86 964 414 892 429 1055 54 379 995 838 9 99 1039 1052 967 250 253 639 271 131 1027 348 785 744 221 84 501 962 734 815 523 873 146 957 28 599 893 1114 705 766 737 1262 680 664 526 292 915 1154 938 17 367 358 1054 679 1256 194 922 1085 655 480 8 907 1127 689 1146 424 753 1104 1246 169 1112 692 35 1017 1005 732 1151 795 171 1058 154 1133 1089 46 801 43 525 999 1205 1137 770 1176 67 134 1038 669 771 331 1123 140 1118 1270 1219 826 733 807 1101 1264 849 443 309 670 1001 1233 1102 615 706 49 255 248 405 603 1255 651 703 142 1150 1263 973 209 945 374 683 1147 1248 1117 550 1135 864 1231 606 174 808 222 47 127 19 1050 345 333 742 587 1198 871 359 498 727 1081 963 5 244 413 573 …
Output: 409377

Example 3:

Input: 1604 1141 1534 483 1378 1262 1388 651 1498 717 1442 1273 1198 830 436 1573 329 29 501 596 198 365 11 161 424 371 800 1531 675 1207 1551 514 962 1332 694 1444 1271 280 598 209 1189 1429 1377 1336 484 59 757 1357 164 324 1081 310 17 986 1290 1483 174 1425 1048 1055 309 718 1373 687 542 1320 592 588 731 4 115 1335 1463 1563 1085 1178 569 99 553 758 1592 633 165 1584 1415 969 1308 1376 300 1102 450 16 1174 276 1011 715 505 40 285 685 206 1136 1454 34 1559 563 367 416 286 703 610 538 722 935 307 928 55 566 425 1279 1137 1393 1599 1417 510 253 419 1197 1042 583 581 378 482 708 968 702 1281 1171 804 1432 1049 845 1054 193 1161 863 1202 33 1203 212 1018 887 1430 331 1034 976 235 84 103 885 1406 266 1467 1438 991 1126 1590 988 275 143 1588 1221 1212 661 496 1352 973 1572 475 1484 938 210 327 88 636…
Output: 633619

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Ashen ledgers of Zara - MEDIUM Coding Problem | CodeTikki