CT46893

The Disorder Count Beneath Greystone

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the shale slopes of Greystone, someone must reorganize the archive shelves. This year the task falls to Farhan, armed only with the vials 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 <= 3773; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 394 -316779 -661284 -141367 -100507 198196 -171131 -317670 -943985 -662025 89916 161964 -466952 -629046 744954 536705 -252463 232993 -388009 -42310 112926 -722811 23675 228531 -744730 263485 77660 196132 548361 733197 998444 949471 748008 496139 -795185 512731 -580907 243606 309666 643895 42128 -646706 -930853 -598818 -754522 -516753 -54971 -664922 -802327 -475341 -172269 691496 607684 981153 -387561 -749500 300242 150372 -359788 -165272 368541 -806063 -947233 -534510 539304 -610345 244923 406824 617133 -873333 -551285 790688 265383 -984415 345434 963280 -529516 -785654 -17182 -950296 94794 -674631 55255 270238 -923956 -614010 950374 -843713 696930 772068 883331 886263 -575913 341386 3722 -584937 -152455 -327609 -7953 -489810 753670 -743170 572978 590786 -601888 -769798 -223107 609832 8097…
Output: 37918

Example 2:

Input: 3032 -616858 -591710 -401525 -848456 287060 -949497 -97564 -381330 604457 787633 751189 -246300 -153297 367267 341847 -734763 -568236 629215 934541 640821 -226185 940977 -121640 692520 -705492 -933984 -747033 553474 494880 65897 407229 -875041 96697 -998511 378966 40785 -702874 -97851 -522308 -942766 -338408 958206 -859518 807400 700965 197933 -247942 923644 -746361 832985 -735953 938466 508279 75884 -422366 -379202 -833940 669168 -878789 -502188 458926 188577 451081 641724 425986 606370 -765727 475738 319441 797080 307383 -894582 -963464 -38783 306259 -790365 -604201 -502788 -520919 -806465 -852532 958854 -197265 -387740 665898 -995956 986812 -27196 -259059 -121399 -249866 667846 105542 -850270 416179 158988 506820 -34801 719229 -121024 -401514 363283 -864498 464905 680925 -601857 578752 …
Output: 2293741

Example 3:

Input: 731 686890 -271394 804192 -945279 -421924 64336 227227 427456 -658210 -408166 -782018 -888928 -273316 -828547 139692 711163 341676 520958 479064 -389216 -40677 276177 688601 -684158 273525 -421503 523219 840138 864997 8288 977963 373075 -683635 -252293 -540227 395368 -968324 464764 191627 -763812 -706158 848995 362107 -136329 294637 -977995 239345 -413322 312058 -850871 408619 734326 -707786 -176989 842841 -858640 433493 914227 995215 -205882 425626 969604 -632082 -651412 874451 -472447 -18451 -26783 -911717 544390 -594444 246529 197589 772271 839197 332694 61728 34007 -704243 -347842 -614122 465167 -963244 390075 -75828 123074 832945 608326 -403392 353630 585945 -491357 176738 660755 -499775 -530078 -348352 -787159 -812579 688876 -947529 319646 -622780 -686948 582712 -106724 -19016 -22855…
Output: 128599

Constraints:

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

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