CT42655

Radiant shelves Disorder Count

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the tannery row of Leatherwick, someone must approve the repair estimates. This year the task falls to Rhea, armed only with the shelves register. 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 <= 2141; 0 <= a[i],x <= 1000000.

Example 1:

Input: 1070 70375 923688 928796 156908 962992 699048 662017 794923 975447 842514 539725 478407 511621 494400 752892 9463 850573 558930 214550 920226 65516 86621 900741 730535 552506 781342 227657 525105 236075 438504 451346 740525 957903 379662 489312 859303 592772 418060 570355 371470 670435 599177 99838 893717 680030 412662 622157 130269 899842 535292 938717 405049 498627 554221 768193 409725 614932 236284 798198 694531 792804 808362 931905 368553 873570 678367 851481 896527 305433 294514 739978 303272 565282 577698 568753 328612 251408 245901 789427 989236 390977 532491 724161 849953 302716 973310 852813 636244 403445 700420 348247 435929 850047 853839 764221 481570 776300 489588 267160 800837 413527 92082 497327 764369 402308 436154 954736 665517 872513 458476 125753 657395 25858 128198 22918…
Output: 294390

Example 2:

Input: 623 19051 280538 875581 585743 115966 574896 71200 176024 387456 156249 476259 633044 955761 416865 816852 160937 227799 60576 44668 740268 673081 465260 412184 365083 930059 231095 280529 555349 224473 628030 916226 871294 139613 965700 419876 676035 189762 204822 103564 245620 933535 249389 873946 936256 10669 876061 551638 396516 678933 182878 36545 475405 47376 113012 75777 145689 794463 454241 155448 406882 372343 884684 888968 954636 756592 347522 192908 293789 749885 197674 761460 715209 957642 184460 630369 478372 866303 880273 403499 707340 260086 227954 378337 584975 840255 780660 104689 643441 574861 187885 861026 353088 504926 193083 748581 612355 500702 822917 83134 641609 239050 953690 51094 474541 369798 38153 102625 996377 453935 378890 381658 808294 76542 803249 601557 843…
Output: 93207

Example 3:

Input: 939 20 922 495 394 647 871 584 142 483 555 292 0 877 775 582 325 531 833 682 477 306 97 595 348 408 914 340 887 453 805 707 224 443 58 500 91 505 92 747 809 822 48 915 8 907 17 83 835 272 457 798 828 301 322 508 335 846 7 88 1 155 396 604 392 229 377 581 597 861 664 777 619 233 37 633 424 106 625 436 926 76 662 607 252 826 170 479 936 571 776 549 700 879 658 360 53 731 210 845 214 273 685 222 386 205 178 492 504 297 402 759 19 285 870 869 716 263 264 652 561 407 573 282 729 314 790 27 844 931 498 925 509 427 211 482 418 487 742 450 279 566 281 189 739 501 373 827 146 745 352 930 820 432 918 338 687 336 560 159 726 720 114 434 623 359 240 286 559 543 651 320 261 188 548 823 801 749 73 77 385 270 69 679 493 613 68 741 329 851 75 277 773 167 755 362 257 28 410 321 303 629 796 898 921 929 3 25…
Output: 221470

Constraints:

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

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