CT59224

The Northern shelves of Sahil

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Sahil runs the customs house at the coral atoll of Pearldeep. Today the books show a list of shelves, and the numbers must be worked out before sundown. 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 <= 2857; 0 <= a[i],x <= 1000000.

Example 1:

Input: 763 886388 339584 42161 65644 932774 923779 719407 132167 220134 623718 328479 975109 378088 116522 228955 214826 750955 645455 324174 678006 780872 903970 659497 273194 68969 673210 834380 472622 578699 456073 279375 777589 638362 159411 892348 22067 319350 423720 361053 805865 52130 553727 432281 938790 886610 891724 164254 902975 51620 473338 932081 780919 22633 421709 706568 290290 652669 878145 102222 481763 414590 888310 672521 265855 456760 733632 702049 937371 199010 800824 145574 139316 542585 105087 321602 699333 394046 666340 126622 450351 609943 991420 105706 696431 845878 111298 476536 581091 622875 727336 377177 347064 76807 919373 44416 816473 92660 618702 545747 10913 197940 570587 591442 71470 185031 808971 947902 935010 370975 50024 279025 931933 953286 777344 676259 9923…
Output: 145805

Example 2:

Input: 2249 752864 24394 252231 122732 499326 367950 244753 960794 853258 133299 153984 203856 798252 52446 602819 228260 997220 827341 712348 358459 383943 414113 999757 829214 697170 882507 738877 713146 155879 648119 431220 777620 960710 297414 518712 860752 891069 727431 744964 317141 920930 704777 881339 376699 912160 22080 876729 295396 459267 232035 436770 949792 288492 622491 524640 265634 242735 593262 511742 31315 709981 883724 488161 532001 651494 904026 488389 204884 804974 340116 573363 112082 709573 268184 554392 670545 538104 511847 874962 22658 219032 351280 802424 981203 612120 139012 430545 757150 728003 118621 352853 825496 274140 490272 810505 255722 132959 977782 914585 197993 883034 746539 343616 198974 817632 196322 424570 583372 329459 105271 78200 167898 141256 280929 801…
Output: 1269126

Example 3:

Input: 938 860 823 829 833 493 262 547 248 554 527 116 524 11 798 392 164 194 210 289 840 367 259 298 837 232 291 407 666 386 147 614 119 433 126 495 469 365 932 125 380 255 892 686 14 225 451 92 531 482 323 58 427 280 368 648 937 885 525 858 671 935 804 661 856 402 399 342 292 799 315 627 350 733 417 223 181 82 121 354 735 918 781 538 517 100 250 720 297 618 668 581 150 714 926 758 658 363 434 803 662 815 113 595 752 383 17 706 721 54 548 480 321 385 583 87 448 740 165 51 60 681 158 338 473 760 500 731 745 607 234 878 124 320 186 220 521 749 845 30 620 107 917 691 603 170 528 820 889 8 497 602 900 148 914 374 253 519 626 535 252 929 347 214 761 431 679 422 398 586 32 91 783 729 751 563 773 928 185 741 405 457 824 52 789 675 439 251 243 167 281 216 508 894 188 110 41 27 757 883 572 455 75 827 309…
Output: 214565

Constraints:

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

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