CT48663

The Obsidian Shore Disorder Count

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Nila inherited the mint at the basalt cliffs of Obsidian Shore along with its curious bookkeeping system for shelves. Time to make sense of it. 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 <= 2889; 0 <= a[i],x <= 1000000.

Example 1:

Input: 1427 66364 294594 407329 482235 791956 146801 237875 703505 14617 449864 389904 566765 780338 156432 770978 548894 303340 297566 368198 560953 207133 974533 603273 267717 80761 582206 256706 380860 909599 610777 597301 502640 788387 567820 952556 573136 554036 686481 943789 776116 18506 706091 307837 302061 559556 854904 638740 723428 706114 846109 598906 718510 639130 512108 597864 485608 520602 663102 235811 757037 947431 788386 12957 918279 299761 789037 373087 821279 119351 76278 612126 885990 391398 324329 781437 823157 69659 941636 512551 582055 11832 715342 938833 195934 732347 736353 709178 510070 921654 433055 453011 102987 855501 534106 321484 992965 543393 944790 46051 124574 673435 222543 483062 990395 135300 609094 433926 951391 833695 700441 948367 925770 455749 641786 130001…
Output: 519155

Example 2:

Input: 1497 1140 1335 856 575 378 215 153 40 992 695 1143 1010 674 727 890 905 1291 1490 389 320 1191 1031 587 947 243 1035 437 1320 552 283 121 225 696 390 249 134 329 1281 1300 136 533 1457 278 20 129 408 1187 753 730 395 1153 204 1373 188 1288 264 501 1018 598 965 1292 209 1098 187 482 917 636 784 357 68 1201 1303 477 1236 287 137 267 1199 557 1114 317 743 173 27 599 1454 549 956 948 1296 532 165 945 1270 811 458 773 190 717 669 997 424 1073 499 306 1297 1050 359 1415 1346 1178 938 1468 1252 114 1366 1234 1229 736 1001 595 1338 732 145 1355 649 62 633 645 949 440 604 58 621 887 812 155 1034 182 130 16 1266 1056 785 1105 1072 479 1070 1267 516 922 1264 518 1392 714 855 737 1028 612 825 449 1233 1340 1331 981 761 432 572 1370 95 1245 1007 510 571 1304 270 279 939 268 724 1014 1469 1064 1361 898 …
Output: 548209

Example 3:

Input: 989 847101 442383 828827 375378 851377 579443 260295 673384 772851 236916 217709 568586 791780 596345 775737 623289 589208 909361 685842 623917 551519 204816 957955 170469 358047 433914 168177 587642 541647 720836 344333 500166 274944 115949 961951 590257 657034 897565 968411 173191 13449 735151 419015 293219 341043 662760 519852 802716 291314 695129 43499 752605 778973 447857 476942 97955 432447 50508 529307 625205 139001 700764 545680 144999 744519 969803 507994 964372 92031 212256 11916 818149 49603 141966 603753 85767 354001 538809 732074 57253 450888 540086 297327 593557 808001 128175 72635 557579 996656 856485 469026 224861 852363 359365 723885 977178 396864 297927 588427 339344 874143 898531 983608 393516 469334 313587 374318 643549 799174 463377 20957 104293 295131 394420 574879 78…
Output: 239482

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.