CT53141

Last crates of Rekha

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the lantern lake of Firefly Mere, someone must price the new merchandise line. This year the task falls to Rekha, armed only with the crates 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 <= 2634; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 832 -639206 -260663 -21484 -128665 -60341 -683967 278791 -540892 690888 605157 -50340 -560012 -867766 -835720 398537 900690 -690903 713033 337985 -263040 -544000 -953332 -961765 460082 638260 -798694 -882338 417348 -603244 -151098 -48550 888796 160793 224423 -114990 458493 -968314 -558424 -887462 -1247 501411 335195 -945093 -694394 -668958 857861 692358 800782 -219715 858282 -732798 -58324 -203496 -529932 686460 96224 321647 -832199 -558125 426508 899742 -29117 810015 -30579 82648 47242 678694 -234389 -633153 965597 658623 604525 -564807 -613360 -999289 -193225 -82953 68753 -595509 -415179 -857409 481161 -875567 -718134 -76694 482885 824653 -316812 13581 709574 -683788 -72766 684185 -967046 911559 -652910 -108347 16693 844978 -526509 468409 -841151 24871 176928 -638440 273363 -128692 -7077…
Output: 168329

Example 2:

Input: 167 542229 -118699 407584 129744 -125660 -342030 608145 267019 914364 360394 -460000 521864 193799 -490864 227196 -237138 231319 728285 -94923 -445058 495652 -529126 235364 4463 -170733 59322 -518085 -98184 39754 -147416 499325 215526 -877628 757860 797453 -305570 164028 64778 -522966 -311652 962342 357260 863764 194904 562192 -980174 -242195 895739 302691 -229153 -959880 840636 -273673 -513489 660413 -589298 -982323 54168 -990244 -859670 852676 916298 -721846 698269 -165167 -634288 755747 682389 -699838 132419 347579 824761 139483 -885830 910438 493084 -449267 -405152 -139718 223966 41265 617823 -60494 -773715 -146520 -498913 -667682 -503912 753355 -856641 -120060 -132098 98413 -397238 373236 -202372 644685 134411 990817 -892076 384780 295843 906096 133848 442420 805376 -935862 -987035 84…
Output: 7392

Example 3:

Input: 37 -756115 -566287 -976645 931595 252368 -201710 -510580 -146566 -102620 934923 -853733 335658 -572429 -7646 -119409 -274211 251372 -782118 940835 469521 -547919 835903 948021 760133 534205 797475 239654 -964781 750230 -2996 632431 -118988 -679348 -230293 700612 -539455 622274
Output: 284

Constraints:

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

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