CT61047

The registers at Buzzwell

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The harbor bell rings at the honey farms of Buzzwell; Grey weighs the day's registers manifests and starts the calculations. 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 <= 3986; 0 <= a[i],x <= 1000000000.

Example 1:

Input: 558 701176900 232980364 99253890 257292222 245998347 493600336 96407311 115438512 146777594 329247229 237084751 541113523 741326803 752610380 786784217 88599811 575210065 566435768 938091432 397138623 666385408 584881438 999334154 447820329 796640552 663858047 680169682 84410904 240969342 544073129 369885539 235352869 87351331 952261659 625574122 544058578 807864407 963563460 627664393 372495359 466806824 751728120 647630227 952297803 656409670 888268580 154984179 91206337 825394011 604743926 259401259 576486104 539617457 708002088 790725029 7567456 905059478 608575669 482848721 404921218 390368982 265336747 223398217 949458541 653085841 497541968 251943130 53226749 646766523 637299298 125541395 3456158 56929142 219319389 36165551 446152037 490152634 891315584 898847443 176826021 950757117…
Output: 78538

Example 2:

Input: 2365 729194625 38895235 454843729 239620926 554454836 189146578 251661978 570655236 392589794 444366425 559251768 902808457 987592757 920526475 474498255 642890987 447378187 174308163 817777076 927060745 125574352 658708526 559001818 957735021 618758555 830392078 578858257 557855410 615421654 179526435 195956434 439579526 108245332 108827939 307162519 724140631 322344328 840389902 487150574 642696666 507023271 358487465 384020362 535468189 232666606 600541420 755605211 324039189 813638597 48377251 115125207 21812692 781788441 264002343 274604335 502871998 72953890 732855702 755129267 767759151 452348960 735266167 279965058 193318651 491134768 605247693 519629344 305246852 943580948 735914416 215655672 563942243 588860800 796672878 748842009 103715370 542210716 984057548 602736880 367803900…
Output: 1407364

Example 3:

Input: 3621 336297869 219800677 894082561 744622295 848332890 509315900 630776391 300177022 919857846 115047254 743469637 69483967 859609154 847963696 947148997 152712061 631991433 994498390 752004481 757290421 733275800 210148912 549363304 455229627 244410112 627086553 865374775 64968575 500854033 558999631 822789913 84201764 521553276 867958847 868940166 575427377 945976935 922084906 43752605 629545527 441201258 852839026 270029822 775766166 820665849 674753626 769068878 887489467 790420090 216782996 83381663 287888604 823794762 899865597 204975224 989779228 835699231 471223250 541982737 48509707 313298681 237954964 545251081 991833608 7105368 366751037 630360126 117287177 78485398 572712381 84339480 262781235 895598404 143667253 890763711 925142169 266725685 236721899 498957870 756116741 63567…
Output: 3257472

Constraints:

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

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