CT59494

The ledgers at Selene

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Caravans arrive at the moonlit lagoon of Selene with crates of ledgers, and Morgana the reckoner 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 <= 2356; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 1286 549 1217 1032 1101 647 338 961 1063 828 1168 605 265 558 253 221 1115 817 699 20 151 932 415 188 705 1005 1134 1131 576 129 161 936 726 225 41 774 321 1064 288 1267 70 588 1053 627 846 287 592 878 220 663 378 0 903 930 652 167 1089 670 1118 910 1041 813 804 198 441 843 148 489 1 1181 934 127 437 762 399 1241 231 1223 811 782 713 753 637 1169 349 1133 371 482 883 209 636 44 680 1271 851 553 290 931 81 1119 178 1207 997 428 1208 1029 740 892 717 534 607 765 899 1031 939 332 907 284 1254 865 1201 113 24 896 464 807 1000 142 880 1067 771 617 1175 905 916 457 1226 1099 266 207 117 93 123 1183 766 16 920 1057 1263 504 809 902 602 241 56 790 281 956 239 77 446 1117 1264 524 1102 1266 187 915 522 313 394 777 101 769 829 716 468 301 546 175 1049 729 133 958 1065 838 368 277 475 149 116 254 36 …
Output: 405527

Example 2:

Input: 604 711845832 410110937 126336572 930717129 588573528 882109544 494045954 675493332 785816339 65400206 491787205 449710457 458243173 871042068 373593241 246682963 277779322 504991373 498144410 84589032 169363610 17103971 565107965 764629957 411709072 945747349 11300787 546824075 128136239 527600930 251586544 892571692 888813278 641473029 114995638 28908076 626241711 134875598 93035298 831893969 439496613 806727326 542808325 709767610 135357382 538597919 302391529 933619284 49337077 759984043 612732699 309454966 555730069 282575621 528999756 534415478 749197643 374383551 421619936 714671469 695852825 807599519 56491589 970955490 957939628 125731359 356726166 627405682 949030131 95283888 623631160 798694586 889301173 177771349 385851923 671465235 100519879 898455975 41690898 174091712 470427…
Output: 87195

Example 3:

Input: 913 782 217 730 135 395 310 88 327 629 642 757 549 682 276 793 383 198 274 371 439 398 640 329 76 336 85 433 716 719 565 872 170 223 420 269 675 300 873 788 447 513 477 672 617 558 759 592 178 507 262 623 470 581 517 386 798 840 680 384 550 755 268 285 503 222 246 498 122 902 673 665 599 454 821 19 511 291 725 375 194 731 244 579 94 909 36 824 294 175 367 267 590 539 148 361 81 749 75 796 704 476 740 853 47 692 113 435 437 475 491 309 380 620 278 124 818 25 17 815 126 15 118 136 370 82 205 530 38 89 224 379 610 588 438 334 289 893 183 101 247 326 805 253 869 713 767 137 61 389 55 604 900 666 769 272 458 533 660 241 860 54 497 694 652 743 255 520 729 215 711 572 664 901 895 734 506 59 2 842 263 574 184 385 548 216 566 636 580 726 56 858 606 526 119 879 34 848 831 534 460 586 408 356 307 508…
Output: 217339

Constraints:

1 <= n <= 2356; -1000000 <= a[i],x <= 1000000000.

Loading...
Test Cases:No test cases
No test cases available.
The ledgers at Selene - MEDIUM Coding Problem | CodeTikki