CT59718

Last crates of Petra

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Petra the clerk watches over the wren hedges of Thimblewick's stores of crates. A careful computation stands between order and chaos. 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 <= 1199; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 1083 942402247 415410844 356261049 909813974 188808353 664778800 921330884 290071538 574262771 787695742 457822934 674261583 9945095 550770807 798580996 578019806 951768192 439830147 142176449 23734634 190834842 423647171 297824482 79619798 117040128 213238072 311733941 632819912 523518925 169783228 569065178 896581415 332444075 102637833 526267803 617487125 989583383 940620661 709858289 480480394 818199841 913193697 50944303 362885513 420356055 152451060 940444037 715497674 453380070 541571106 631320862 519083208 917244884 421305687 256695588 69283826 105270173 773070246 512104178 639226579 165810164 345825770 258938300 545853631 908673217 27270849 36500709 478912726 233254520 328208830 499141472 188150832 113694791 726257079 936804509 823822709 751114922 674296455 406706518 487439443 818…
Output: 287073

Example 2:

Input: 593 432316996 130295830 424866826 835743603 963448614 530845616 527986706 22706135 960062832 637140715 740124075 717003319 461865546 515917957 83985282 901295528 832362523 15898442 591370151 367842361 978894046 374431519 247787841 528720948 477084658 415590073 258704060 19727701 417036956 507308580 364833273 978292638 753246824 829610741 911681282 327648115 30400860 282378050 351050777 540570551 946919474 612181220 172341941 725903551 857468717 971535903 146214852 340770388 678152297 213066172 707281212 304980818 610454226 747818848 -177252 917826180 818846517 118385337 850356195 565398787 542034722 813929926 728242794 675113912 592910987 632801020 16210457 809402316 309534409 279084073 150314433 547233015 305224171 226305817 335951354 68647563 956026669 446211192 814320613 739264243 48577…
Output: 86333

Example 3:

Input: 914 152 863 648 857 777 462 15 290 504 318 549 733 865 606 609 458 246 191 540 647 303 183 144 667 206 781 756 873 380 671 258 809 837 506 855 547 650 202 513 155 691 814 633 836 172 393 253 518 669 679 107 397 405 265 596 455 233 713 306 594 645 568 803 203 453 163 461 845 792 194 535 390 74 818 627 682 134 39 550 592 766 466 774 485 177 536 91 291 332 234 800 694 772 896 532 352 2 819 644 287 743 31 729 64 65 614 890 295 665 445 28 123 394 503 468 764 438 583 109 90 768 839 53 426 831 736 763 543 776 618 577 149 62 693 794 690 54 832 319 271 907 441 71 897 4 354 757 119 118 136 418 624 381 726 779 8 416 778 838 551 67 260 740 94 186 95 707 493 112 526 128 544 434 737 425 515 613 145 81 237 797 251 842 821 879 72 529 29 574 218 235 722 881 752 522 552 427 488 849 528 491 209 724 93 10 40 …
Output: 212371

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Last crates of Petra - MEDIUM Coding Problem | CodeTikki