CT64340

Farhan Counts the crates

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

In the tundra station of Whitesnow, Farhan the inventory keeper keeps careful count of the crates. assign crews to the morning shifts, every figure matters. 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 <= 2596; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 2077 -934700 -879614 -361884 325289 -67718 -118909 -892758 -232457 986561 929263 -204246 490788 946758 433179 -195742 931854 330240 -834874 889091 -184369 -751661 -876718 938781 -150637 635191 634143 -796991 -795997 260154 -892164 735117 241426 -632286 517443 -870020 305628 -726920 -71149 -732291 471615 -586700 -544449 419256 -298162 593619 573538 -934708 776596 -837230 -575983 717177 760873 407386 -781174 350267 -371244 779765 752934 105811 626832 -148293 3474 57261 -13427 -291571 642719 650319 -512378 537941 141907 688247 -266539 -521915 -652574 -44588 568299 -946976 -584504 739234 -53840 -780179 -686840 230372 15663 -996135 339223 502575 -609600 998450 -947030 -928692 -388391 -757021 681768 -263783 736327 -576792 -14158 841771 -145498 -600438 525811 549635 -674487 604735 -932827 -64664 …
Output: 1071874

Example 2:

Input: 1857 713645 532268 -276690 -361316 225687 5560 286551 -210199 -477985 -175291 -487294 11257 849379 218136 471134 661959 -588603 551837 -911349 411228 -562833 139425 -154111 -60141 673927 353394 -600227 1435 -541717 -677307 -445610 -895675 -698993 697422 297140 -570065 817895 641862 -877717 654182 -233606 -163357 -278395 -63398 -64595 -849105 216525 241664 805773 -665270 547849 158359 -834837 -95419 -239212 -700691 673121 693170 149528 832173 -588036 939817 -909006 804118 -720397 -757599 -954845 -705378 -643009 -554284 -556299 -824248 622007 123239 -220815 164933 -732100 330849 -691665 898528 8435 -500204 229873 195800 -153271 700631 -103732 814476 962705 440748 674156 488303 937804 13889 902319 393661 684727 539120 -142797 -592223 -774716 484280 122819 -269491 911481 824945 528822 -185376 …
Output: 860217

Example 3:

Input: 856 -788727 -1496 -32601 -821745 644420 -111355 990556 902575 16684 429312 -519530 -552570 -905894 270995 799860 310578 -281862 593138 -802232 995428 996753 -94 308899 227462 -415068 795136 -42848 -860818 -702289 -767015 843774 899759 -648157 -183835 358331 -476199 -365890 -966868 -445047 -216913 -128893 600265 -35690 726220 -286759 -923989 778838 -722872 -334816 -583243 -721140 -699902 435492 518248 709744 196523 206755 -770104 349517 -642248 216776 368978 -376932 959242 -274088 -452671 572197 804625 -58893 -490945 29680 757173 167747 -831187 -112789 507820 168214 428598 -167336 824356 -678709 -32320 -371677 392416 996468 -518433 -509858 -590998 -595061 606360 -224624 77447 -579128 -670185 274811 403383 -965905 -363947 685306 768824 -190700 274390 255446 727923 -310739 -399006 -649577 -28…
Output: 182927

Constraints:

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

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