CT61155

The Disorder Count of the Scarlet weights

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Every season at the mining town of Ironvein, someone must document the rare sighting. This year the task falls to Hugo, armed only with the weights 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 <= 1669; -1000000 <= a[i],x <= 1000000.

Example 1:

Input: 813 458 812 58 422 110 138 569 147 327 697 304 107 550 762 801 429 495 371 226 222 131 772 91 134 508 273 573 106 628 164 726 63 391 307 44 605 430 592 682 405 247 795 678 369 426 347 577 479 339 578 561 581 761 89 143 758 40 681 549 634 537 709 59 534 636 432 177 389 477 712 236 584 359 767 763 109 373 470 293 528 732 309 638 25 556 560 316 127 453 43 118 298 376 740 728 319 803 30 811 546 42 155 21 260 708 659 121 388 332 111 139 23 125 540 39 86 510 706 323 519 392 749 716 694 679 490 647 265 92 11 380 229 78 321 524 806 6 575 563 279 192 735 589 182 99 643 185 595 703 742 199 431 305 74 186 68 521 210 419 162 434 197 751 599 607 176 721 115 656 303 174 292 203 714 455 705 393 688 715 156 764 31 548 179 350 473 675 385 564 103 720 642 408 625 790 493 580 622 256 337 794 798 504 461 64 2…
Output: 168590

Example 2:

Input: 1093 -541699 211689 -713196 -447574 380185 -562120 159824 -857872 -993492 -649853 -696425 442802 137228 345415 -184184 -64563 -416609 -268431 495777 -599835 -136128 674311 188691 1767 122506 -342370 326807 479561 16013 -955239 291479 188673 877148 -54905 616548 224879 -251528 878395 -951124 -11285 948216 828886 732272 660577 -249544 629787 -394349 -790082 -279922 327336 -173552 957493 -511091 12672 286555 -211971 -394515 -29132 878880 571237 846640 225338 -106076 632448 766718 241920 64040 -421205 901763 -864092 226913 608204 -784294 -507474 821410 -418872 -839861 -516005 691162 955073 585299 -46573 -751088 -21487 152211 -876683 8171 357653 -110157 -323534 -102722 -470365 -159005 -545176 -615033 14514 -586814 679202 776303 -717419 320494 766946 37752 -427776 232829 210243 -535330 -574688 -…
Output: 281396

Example 3:

Input: 1014 36 536 971 594 315 256 293 391 678 475 989 250 143 658 435 629 848 749 452 946 829 941 109 995 937 344 964 302 225 53 443 119 102 184 604 172 929 790 878 157 823 954 939 660 766 151 415 480 928 343 332 393 821 730 996 13 688 610 8 400 985 46 372 896 353 196 495 345 200 691 47 330 226 255 278 280 270 711 240 722 159 258 909 295 638 137 422 920 836 479 845 100 617 398 926 176 24 869 461 705 106 175 127 800 338 914 219 121 186 22 236 235 986 744 729 888 557 772 809 158 974 541 740 287 187 433 228 643 264 857 412 540 670 310 416 473 215 462 349 573 867 73 49 903 324 368 710 314 243 527 313 356 101 866 252 55 524 589 894 493 597 81 987 213 339 390 910 414 93 467 304 481 424 752 1010 671 360 571 501 440 719 767 1012 804 489 268 381 402 732 395 590 469 170 698 459 905 835 864 57 546 294 450 …
Output: 251294

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Disorder Count of the Scarlet weights - MEDIUM Coding Problem | CodeTikki