CT62170

The Ancient Disorder Count

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Deep in the temple city of Sunspire, Cressida studies rows of ledgers 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 <= 3079; 0 <= a[i],x <= 1000000.

Example 1:

Input: 1664 808631 423109 171896 710674 227817 90317 657140 144937 579977 399360 528777 175199 171780 217317 505934 135253 601603 937321 548365 857423 536604 740424 529685 572337 278988 515703 941198 230889 954200 729832 436241 696408 723249 927263 27959 788186 138449 216424 995523 516673 37455 185531 47204 525452 921042 124709 360362 573600 1143 945004 919186 269441 751982 799375 808118 617782 373121 238341 972265 406729 445233 218293 975628 233140 356303 232480 481812 172300 95967 789056 836934 989489 657236 492479 969994 94762 31438 201882 332745 638439 76219 157322 699025 461794 384214 877289 441154 484901 581999 700195 66994 434151 711400 482680 671004 859081 338387 244068 823416 440118 665278 998578 423821 453125 714597 298596 918184 730489 21170 457419 540413 506909 539822 351774 733796 59…
Output: 699171

Example 2:

Input: 2510 824798 114791 688592 703917 850677 758316 374105 289082 74371 477302 223621 626734 147445 408633 689999 678539 529439 530042 230908 853510 342373 197112 71683 590293 187056 780467 826097 17093 740585 550097 968405 593063 884680 225060 230286 125729 789543 57849 369905 449876 421910 608084 485957 605061 347285 950148 359647 390293 367068 51119 374104 656103 69409 1357 673501 108848 967505 906268 412826 511210 199601 815813 394302 399674 609690 922173 316822 158359 221934 44311 44333 962299 269421 733016 589989 365113 661278 483595 266705 837481 621556 589715 24827 48008 34176 755054 601456 66491 798853 542356 383612 886916 279554 249349 732117 143661 792238 771476 537006 774709 486559 764622 974140 877448 782461 124570 684861 825729 225010 362990 384880 999615 285315 711716 660135 7009…
Output: 1568812

Example 3:

Input: 2683 404273 535249 707586 855887 201466 270442 23919 749531 415631 392539 715668 330531 377469 655511 8686 881256 471727 781379 648153 74430 615317 832038 470254 467774 58760 276706 821833 871077 613959 869521 886817 264821 888893 645221 32357 784719 366225 923011 863302 749794 4101 268233 921506 230430 678620 864275 615647 666199 80241 202039 242187 28670 443327 811247 232410 882139 23711 21195 250497 885671 606894 566992 507261 13969 186944 460961 344369 166415 886170 685621 900784 308139 348455 26617 681950 363009 126857 243818 696561 442225 661811 175353 818863 230834 181263 988388 77332 308524 227440 159565 155072 910038 475407 197997 891065 162514 59706 891189 807280 728170 235931 626776 565606 827806 793606 524062 571070 483777 651184 200798 708903 446059 609114 483455 999167 805164…
Output: 1773753

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Ancient Disorder Count - MEDIUM Coding Problem | CodeTikki