CT41375

The Disorder Count at Crowhaven

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Deep in the rookery of Crowhaven, Morgana studies rows of crates entries. One clean number will settle the guild's oldest argument. 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 <= 2716; 0 <= a[i],x <= 1000000.

Example 1:

Input: 386 893616 71951 96656 228384 483102 789654 376230 126220 106321 819662 482974 698953 758396 303700 558011 733044 541144 242316 408439 41084 671417 671149 826179 335253 947116 837404 816519 299500 251657 545307 7905 446309 475375 941935 389836 626261 329823 376178 59895 356407 33792 972576 516327 593412 875127 506256 633927 891949 492870 94590 748024 230399 574492 569692 682036 446619 3359 235533 282722 91166 111075 592229 568944 362924 327248 517897 584571 161539 227533 528230 600227 507266 832973 356361 15104 15547 408998 397391 250262 241572 122196 5199 826455 354231 456781 271838 75643 441715 548838 744468 680850 224883 966613 635874 944487 866056 104253 352831 899091 339422 552363 694690 36397 15590 153851 325183 201225 510502 354939 155219 590358 742639 890364 471220 886991 76302 133…
Output: 34490

Example 2:

Input: 2682 977385 61276 404698 848778 551773 704250 886862 66035 335157 329532 820074 573181 185337 59205 932920 592787 240724 77413 760104 998646 59189 511536 824681 256937 308100 91273 153441 697501 854218 726650 233164 318483 562440 232278 153164 768519 409169 91755 480821 351997 783723 305291 153596 267417 848995 14074 487682 217052 599395 6652 914282 656786 26549 298434 679648 415507 124582 550435 150133 743216 415783 462412 21041 945639 104580 676162 549911 246836 185672 549217 51681 742694 827042 157321 779754 700486 320810 715800 399969 25073 728657 400552 296554 767428 646991 231201 596844 932481 351964 924782 946608 977199 259840 635894 600145 969559 517323 519666 92602 102646 764517 174718 526920 833860 277865 336956 424854 231083 732825 934596 434814 318893 496623 591253 237420 77429…
Output: 1772721

Example 3:

Input: 2487 97225 998804 107495 908285 881213 989463 849765 207982 942693 184190 537005 835280 115492 523305 126030 677733 491048 371468 555843 119095 281467 473083 383349 192958 872084 124052 469252 715527 483093 176481 885361 633587 147915 261454 495268 402440 769359 939511 333044 771070 168426 567270 287586 416465 325073 943043 881891 764846 918397 479750 9301 9259 365215 754207 214818 552995 953201 946397 270952 479139 436781 980840 148939 455326 688293 757885 319872 146210 687704 56819 144625 996909 892536 738203 117830 810146 452351 860301 45566 211557 703128 986807 485513 496537 941448 847016 199451 900200 815736 586698 169686 889852 328416 421388 813471 730467 620301 326209 31241 786532 709786 807950 319029 350953 132012 178870 389713 618026 81765 121499 652409 757556 158004 150921 304052…
Output: 1584851

Constraints:

1 <= n <= 2716; 0 <= a[i],x <= 1000000.

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