CT62187

Boris and the Disorder Count

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Boris the valuer watches over the wheat plains of Amberfield's stores of ledgers. A careful computation stands between order and chaos. 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 <= 1462; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 940 821628653 229298974 110898980 184301415 831541870 109020651 23284267 554831017 133109105 590286434 816126688 869098190 238215045 838632413 330059342 619716555 480102110 834396674 126509801 446074815 924750024 747598593 142527390 673556648 538741507 434153283 965127749 315993893 367755506 351270877 723832025 146471782 226447936 399311724 640473194 137543408 357788404 97278399 718483051 363397275 779511970 106911022 797129736 386935015 255885543 632094741 688200125 889354475 461532574 140276726 533983166 46439608 288805598 856630411 122710879 757485244 302637658 865266892 794335279 335901641 488346413 981574489 552337552 212680670 588537190 376689562 675820650 901684037 73289166 788383658 914805086 136811005 226170382 621344915 321355970 903739529 390452517 262039168 157677992 936124322 …
Output: 216291

Example 2:

Input: 85 500517220 735951043 48356877 814491672 291061856 676838001 120751923 821054194 14597781 184700428 526559258 224960898 574107138 230185572 821291176 528715517 28829202 698399848 53063862 831585409 340178346 854840553 608092730 827527492 537625955 798433662 967599720 553911661 654302245 888970083 634008268 6465162 448622119 962272479 631967752 608523387 14450028 566043141 387509767 708109605 981033350 234475989 790137657 157784616 712290853 522348754 219730070 797463524 853849766 609737149 619415705 275420722 552538988 500472958 379089845 928352919 848356749 444575273 654977411 361047443 269337603 529012190 671116153 744542818 329996010 420200328 569016897 456958032 999307934 156518819 594492774 5684975 534813434 133376233 536740066 320132645 400445522 497590515 13861590 416883692 9052482…
Output: 1809

Example 3:

Input: 882 372 565 138 176 582 61 364 8 162 366 255 739 762 19 87 876 476 469 192 828 321 244 520 276 554 254 791 639 612 661 656 429 85 571 778 728 627 213 659 214 590 215 730 831 471 673 480 284 236 312 607 377 302 606 710 568 838 843 547 38 840 310 807 205 62 704 742 645 687 318 540 691 811 825 504 306 750 249 622 551 355 303 332 848 694 511 282 228 232 436 824 30 296 277 879 613 651 449 31 774 665 421 683 352 784 114 635 104 147 720 75 705 174 655 777 454 599 73 509 539 779 555 680 390 592 12 755 782 707 533 479 621 7 668 557 149 618 186 869 501 587 724 409 222 280 598 309 880 536 486 653 736 44 796 790 558 331 535 690 208 512 768 155 187 272 502 757 373 677 263 146 21 133 169 223 234 55 383 465 334 608 209 463 816 300 818 339 243 349 217 405 6 379 868 68 189 41 385 342 66 376 136 714 368 636…
Output: 199095

Constraints:

1 <= n <= 1462; 0 <= a[i],x <= 1000000000.

Loading...
Test Cases:No test cases
No test cases available.
Boris and the Disorder Count - MEDIUM Coding Problem | CodeTikki