CT60445

The Disorder Count of the Indigo crates

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Jace inherited the boathouse at the shale slopes of Greystone along with its curious bookkeeping system for crates. Time to make sense of it. 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 <= 3452; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 1653 409483669 119170622 980969266 508641428 687762688 291043638 72345274 828586507 682748338 212399008 514814086 362189166 897665338 413486192 397745467 568562190 904069878 298088573 251739826 771498800 421729781 520958750 852838196 790896411 266045129 294555367 383402075 260295555 698701169 870579263 584340231 591230582 967706383 805600957 480952967 898091913 440032477 367879340 316659027 858922413 623975711 942982296 987869125 235976409 478803814 123567008 167459036 377887749 955656988 464180405 40086451 520396374 855283797 878683867 486666785 648239028 666986709 564780583 590225278 136869879 672956905 121933519 881002943 959106902 534931861 562091228 671155855 507337769 320964943 382396385 793297063 517945253 578951726 938171624 627748602 834281783 757124915 537476701 268813195 8364907…
Output: 688847

Example 2:

Input: 1717 718316179 997891720 549297872 169295022 14804806 782397949 280802808 994488374 452467141 500526134 908836506 835885322 227201366 845172163 817521781 342996073 89402970 262133174 977286056 598281935 283109651 767532901 565814560 59659969 705129949 536124999 519856958 426991014 26289636 734545096 672246152 491890130 117584574 353364932 647859724 988476805 207653030 427761831 178633967 210880843 922887424 587862855 935629848 320226782 704810397 305428333 801584928 931873051 981489226 616668419 892410363 634339597 482794410 804495228 556681878 39942178 551484859 651089333 673492193 81002805 204054015 203315052 887808700 635415349 629661240 663098849 880189095 129676093 412640049 172068424 357143324 196174281 618599108 319676643 45171315 601751791 83343972 280585538 254883497 222097581 988…
Output: 736745

Example 3:

Input: 2697 580016462 366688600 16446204 150199835 820775760 934627848 21518967 575336254 99574562 827063342 130744139 262295907 638124641 584010663 253235322 85790413 127738819 850067792 762069455 272088891 343191621 763637679 216347379 348724174 71226072 259402862 815579296 677347881 736633999 439614281 764682482 787796435 387918352 236137120 553169737 547478064 527031110 310173439 505758937 787365533 944667969 131505244 338011857 846135560 115635537 454610581 592696888 311502766 102549911 798773801 196838162 5198105 235288140 472891122 847737126 357288712 345407879 450922458 382794724 206362071 935931298 155041702 179232843 289822630 249172406 45940271 703309676 39387395 756158274 841217638 519494545 387944878 377932317 984569786 472033840 35318585 121124852 47583552 704246538 628539258 878454…
Output: 1825991

Constraints:

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

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