CT40744

The Garnet Disorder Count

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the lantern district of Glowfen, Darian records each ledgers in a worn leather ledger. The guild wants answers, not guesses. 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 <= 3375; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 352 -352912 751243 520156 -600983 -816265 -42271 -248407 506227 274870 -833898 -324218 476632 53286 -597810 858938 501277 -459377 235755 25554 -724943 746296 362492 558750 926560 735977 223634 -77070 580529 -186910 -809505 432765 -373695 -649349 105576 772917 674385 -239723 -326026 552358 -776340 -231830 718897 -470297 525009 450518 -230424 -73118 675681 -767799 317654 -302627 -667561 315217 -693171 707918 830557 -537026 -338964 -722409 -642066 -274121 -97929 337043 882080 -317490 -339277 -944783 -989824 -677258 279791 -291804 5006 -359161 519854 -616131 -399905 692160 506669 -892038 350703 -176868 211239 23873 -574335 138843 -901604 417997 -649895 -452214 675519 191149 -993719 -839479 -420851 278772 -962375 37138 413461 -799831 379187 -248084 610539 -5899 523630 151944 186944 -393933 7554…
Output: 30440

Example 2:

Input: 1590 315088 408052 16228 713771 363841 -615744 -700448 -146011 206515 -124995 819864 -687092 254940 493819 -82863 -122027 492999 -917620 835443 930529 -863818 885579 745328 79124 327284 -822234 -679954 19762 -828793 -882392 -119816 521427 -406578 973054 312168 -916995 -655821 -566609 676164 -167060 -801518 978498 908566 -181548 535315 -71627 320751 553003 708176 640978 521151 429430 633194 -84244 -823199 -693469 -881167 -632824 -770563 -780619 910377 -120317 115627 552913 870444 -369654 712512 -51146 837902 -296047 -142279 921606 703475 -699645 -847507 268795 203120 60814 832495 -924366 -804584 -953725 -946629 -410509 96859 657614 -435360 -283558 681514 -805102 -888954 496375 230177 -636384 473584 -895672 414302 154783 -462537 -40515 -715050 129381 -491659 -377987 -283756 607162 -619854 -7…
Output: 615073

Example 3:

Input: 1035 313818 -251310 -448144 -528340 783093 -769332 522688 -62918 -317882 -442164 646699 849130 465693 -835046 -802454 -427841 -27379 -629106 -772629 -126596 445156 -792087 808607 -530383 603140 501661 -361785 356095 101701 58217 -695297 85534 -195114 -89153 -608701 -677525 -117966 -691274 483790 200428 -634147 -811157 -454645 -865194 -693030 -885755 579061 -648370 -246877 833956 -93323 443029 160265 -896102 874012 -103977 -652422 905659 -356132 931446 71312 433944 888814 -107625 526245 132230 477543 497780 917743 -946542 -587060 -873562 -693697 987561 874416 -968320 473617 -824994 -996731 178965 -392697 -983299 -837934 446007 -109122 -826214 589923 -288401 414955 829720 -475353 -298747 -230553 -831550 -144998 382621 -983618 -530153 653951 889167 -823767 69201 305393 585358 -721089 504302 9…
Output: 269984

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Garnet Disorder Count - MEDIUM Coding Problem | CodeTikki