CT54838

Faye's Zigzag weights

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the orchid house of Bloomglass, someone must recover the missing manifest. This year the task falls to Faye, armed only with the weights 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 <= 1647; 0 <= a[i],x <= 1000000.

Example 1:

Input: 145 492295 995475 455748 773240 664404 150768 345705 482309 984881 791122 684931 523093 941965 471737 293429 84601 575819 542191 823074 602534 843009 264079 392661 515436 213434 214880 987344 131744 86137 181924 70474 331438 353509 354858 135785 238993 401124 246231 713462 94470 388493 685736 863572 459960 322524 376317 829208 921681 831224 921336 551760 369026 719837 783147 794104 932177 311214 527325 190586 744275 666607 477833 200917 984695 433487 337036 884359 482102 781344 866001 556118 614798 13304 550854 214791 187891 68756 142343 81595 282284 270821 240418 773826 930583 763771 727849 588562 649560 757664 707772 455542 881636 283034 30840 762767 644393 490619 647724 631467 575380 45037 96304 556942 816362 305276 214478 258629 95551 863984 620563 717861 667611 859085 204168 496498 47…
Output: 4907

Example 2:

Input: 131 192319 823203 829334 859455 345661 48816 750610 439089 652032 32347 792558 267138 2939 72924 640399 76310 824020 71104 642157 363499 29227 464951 648875 69483 610293 426538 201230 227977 191766 751725 907050 170186 46981 713226 944441 206712 494434 165266 369602 539657 332768 206002 98402 700780 30187 239858 506334 945049 889796 972365 925409 381644 492521 686681 718881 215765 552603 50609 46099 909540 75714 87668 497112 905198 241277 933309 886146 741272 348769 752105 616501 910601 345693 132230 236467 661382 121835 757505 206078 766205 884946 707411 538739 179854 263684 479843 22899 454895 623781 396446 331402 63652 333609 106264 411827 144229 314673 64635 759162 966136 11674 257918 638827 973303 272029 276647 272366 885400 329636 343651 587540 715878 526407 527329 403825 79828 86655…
Output: 4015

Example 3:

Input: 1107 826534 703019 538991 42230 451086 257638 63396 235189 235828 159909 406096 675008 740936 748606 473645 387526 990922 918602 515387 217556 722892 441056 158559 250836 592538 198927 931853 174886 534325 317099 801357 761735 896060 575654 775461 600284 812533 201481 886304 891940 157770 485384 324881 935086 198588 254036 710335 199869 445390 834897 270602 539087 881198 724188 320501 563614 371530 155190 384600 150543 484687 67328 902946 777553 654011 818041 554704 127504 794162 841965 261760 981150 595558 9881 784392 156966 924981 256228 208238 569662 705099 831907 554845 83614 704278 403297 622333 267655 777434 60237 748848 343335 218019 43289 459552 931897 328506 422800 47432 311011 213950 398193 618721 449313 332011 157320 517770 462649 800052 436594 701651 465084 535308 877565 148872…
Output: 311674

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Faye's Zigzag weights - MEDIUM Coding Problem | CodeTikki