CT45601

Wynne Counts the ledgers

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the boar woods of Tuskmore, someone must prepare the expedition manifest. This year the task falls to Wynne, armed only with the ledgers 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 <= 3680; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 3192 -359690 -874043 282269 61351 878964 -962322 897508 -537395 608179 -613243 -997299 896406 24831 -452664 -580726 -793070 -736099 -553901 -285179 752802 514921 251470 -526355 -452963 -495508 276810 529132 -573643 -427548 919328 -226882 -800706 -495271 172890 -291137 -482671 -958326 683230 963155 279331 569167 115033 888381 173450 194592 207383 -193706 -128079 951186 -475528 448525 641195 -229594 945313 -31702 -757992 -470043 770651 177328 -999298 148247 884668 -646222 981295 -785300 -574745 170127 715626 -788052 -688870 -123777 497554 336243 350935 599003 -95609 753568 629140 384971 803301 -27629 -241586 -358699 234727 319361 -388699 -162367 883080 -597206 876213 965223 -748292 67933 474290 -779873 694147 834178 241227 148190 206944 504893 -674056 208280 275519 943427 -177916 -302704 -10…
Output: 2549881

Example 2:

Input: 3529 -535140 574293 202764 -125840 -85541 388650 529738 -431176 911424 -604632 724753 -213028 725587 -315805 411821 -885411 -149566 -730343 581855 -619975 540373 -134282 662416 -473572 891292 -162611 -27025 -380426 -861130 551875 -695998 248882 -366432 -355291 803811 -564879 766563 343603 262766 -181600 155884 517940 -278415 -612644 -951968 929614 148913 737110 -725397 -827412 33391 709246 957024 -761321 -888340 -803516 -715474 896833 87391 -336433 875508 156745 -45637 -779193 -37008 -58066 -442182 7954 -27690 731142 239537 911937 92251 745459 -659855 736622 154001 -416834 -654770 -71659 347135 -304208 196832 364991 829794 954581 145735 -227238 -202475 -412013 -498176 -452255 -998421 919805 130921 -406845 185648 -493006 390217 -787050 81442 -37514 -476078 -919480 -533548 -574081 -250008 -7…
Output: 3068148

Example 3:

Input: 1962 -97235 567462 -890729 -972679 -770704 227588 225171 -202819 566027 -274580 4672 135315 -446884 -99540 -332145 -80362 -691685 388259 874104 722178 -954759 119293 728975 -271705 -990200 77720 -53412 -234564 654132 55244 -550247 320463 648721 -573533 -119200 -396753 931749 -325492 656508 -99891 -47501 -59268 -182862 -939547 -991766 -356951 -383437 -22964 148560 769363 739704 -36516 938741 -664112 655573 410703 -540768 79483 -918246 654662 343036 193813 -672564 -926297 -743581 833650 -516788 365221 -105913 699371 274007 -602018 629404 413761 103262 840479 501074 382377 60952 -235739 169917 -755382 -437326 -246058 980626 433014 -961900 -748565 -304290 463613 -719578 -282491 -62651 -800637 -973939 860812 -968489 74784 -995444 878170 -868373 -867891 -200030 254677 372483 -114933 -536420 8359…
Output: 954999

Constraints:

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

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