CT37960

Ivo's Rustic crates

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The harbor bell rings at the ferry landing of Crosswater; Ivo weighs the day's crates manifests and starts the calculations. 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 <= 3753; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 3646 168432127 467966993 643548943 590573705 3078932 151392907 639676687 773520820 963864857 269936988 750718593 236434264 913573948 646518566 577538882 473913088 499589553 628656236 832073829 969859717 766660925 315257764 723495015 770172947 661546315 551877992 897577203 232593323 988816468 589808867 788130589 400254918 17474039 216053556 584916835 828845696 141152632 921633127 437389446 379074232 210030569 749333291 939290086 984190495 473693261 794965815 64378681 246847556 571526871 443210755 925575832 897424736 953457673 312498495 155844396 257828430 110167999 936170139 769686025 958566957 52597692 752398433 605232629 488847962 365274228 159000328 959080519 569827240 430854647 857432217 151233 536897846 492533919 380634889 888705075 527670758 146159593 511103768 66574764 391650396 5106…
Output: 3349638

Example 2:

Input: 1317 665589546 731936066 511796737 723523011 637276423 754288497 800947308 511649545 536911762 461209289 738285783 397269423 200232797 647405535 196541768 185924270 887183280 37073377 173392944 719116392 188443741 160467876 620140810 55406309 265128505 517894466 302534698 766014658 858556217 525847157 560740661 219915559 410655563 193643043 405469364 673454085 158980041 703665423 283977487 455810867 566207627 926461347 584687552 305743599 699144201 979838340 448272717 633997990 599704698 492554343 679452707 34954685 175130638 767068682 773732349 338884076 553135872 13968177 785149151 235902096 786966724 919059507 630271761 6829889 911125221 372885712 207631736 738138783 812913451 884778845 242611044 280715910 602748385 137578438 847568121 767624418 548971171 957251981 197664231 9749409 329…
Output: 431774

Example 3:

Input: 664 395798913 59946167 347214487 3117127 25339417 398855367 366859811 306079493 943845484 775997251 807829537 222970851 896033326 488048212 350829335 820062652 379534271 578964233 75669313 375489108 461907428 580883198 357473398 42714253 876575141 225441996 366030276 402511197 833582751 838122627 343210691 243914573 172441839 59642583 219980453 880251204 606145727 839318505 430579410 709718235 12727940 91518839 312585953 431827105 108907750 684100060 670442137 214692532 395809805 566277642 436398441 184780569 79532808 703818135 613013188 319318038 778224986 42519678 889788653 703979100 599520464 955850042 694588151 965599945 583564013 879960858 880037197 838626576 689107980 458777164 719910624 905757510 507330919 469783068 31175011 649962069 221908338 528047760 682724819 502653005 93384204…
Output: 109291

Constraints:

1 <= n <= 3753; 0 <= a[i],x <= 1000000000.

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