CT64985

The Whispering beacons of Petra

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Petra found an old ledger of beacons in the depot attic at the cliffside roost of Stormrest. The margin notes pose a precise question. Task: After each arrival, print the median of the stream so far — defined as the element at sorted position ceil(k/2) (1-based). Input format: First line: n. Second line: n integers. Output format: Print n medians space-separated. Constraints: 1 <= n <= 4000; -10^9 <= a[i] <= 10^9.

Example 1:

Input: 3123 645181667 699481049 803581267 545184708 -678293660 -537193203 344578394 909157730 -851208356 -180866255 -253861526 65233762 -273774647 -740875018 -596832704 -620445997 -132238607 148731959 -662932975 695731236 708279065 -134778130 -698334637 850232229 266177991 794347855 368951781 -167959984 535497292 31856262 -31897875 -222759818 800663600 509330665 56342170 743365816 444292894 469896220 -163482533 257006097 920482960 169182306 -586401641 352641024 -871904004 -505549174 -433484261 709665306 -189387423 499903951 -331602177 -664974841 978832783 -166388153 226497763 274930304 602993418 -361308060 706209094 -71140532 395202931 -311355690 -585847713 763244971 -894399618 648717201 342778631 -680452552 -634650822 -368548223 878226240 -451768755 -267711437 777406290 -834469195 -333059960 358…
Output: 645181667 645181667 699481049 645181667 645181667 545184708 545184708 545184708 545184708 344578394 344578394 65233762 65233762 -180866255 -180866255 -253861526 -180866255 -180866255 -180866255 -180866255 -132238607 -134778130 -134778130 -134778130 -132238607 -132238607 65233762 -132238607 65233762 31856262 31856262 -31897875 31856262 31856262 56342170 56342170 65233762 65233762 65233762 65233762 148731959 148731959 148731959 148731959 148731959 65233762 65233762 65233762 65233762 65233762 65233762 56342170 65233762 56342170 65233762 65233762 148731959 65233762 148731959 65233762 148731959 65233762 65233762 65233762 65233762 65233762 148731959 65233762 65233762 56342170 65233762 56342170 56342170 56342170 56342170 31856262 56342170 56342170 56342170 56342170 56342170 31856262 31856262 -318…

Example 2:

Input: 457 -353744927 757825109 -333568433 808911838 -616808594 -731340760 844283544 702267267 -439091866 -42604407 -763083587 822766538 631849901 962839868 868996750 -992333035 -178705934 -488000931 -3697606 -963435994 301641358 371358925 88331235 575681782 -830172553 -111988435 -328137451 -814398218 -349043087 -870546932 230645536 128799707 -757320133 34213743 -295511390 482238233 -156908937 609613205 944919877 811051755 -707698619 632603106 835009689 -453277808 -881849769 -292806041 986434334 837356509 -646054449 964118462 789076548 996860311 -66058386 407569667 -741550928 86809217 978696420 826849371 -514801894 -684406174 -868368194 154687502 103332728 64055282 153935438 -790899803 739310411 -963898291 240656669 -684283380 -806687247 -435063163 662244568 -135997407 -567539196 927150653 469205…
Output: -353744927 -353744927 -333568433 -333568433 -333568433 -353744927 -333568433 -333568433 -333568433 -333568433 -333568433 -333568433 -42604407 -42604407 631849901 -42604407 -42604407 -178705934 -42604407 -178705934 -42604407 -42604407 -3697606 -3697606 -3697606 -42604407 -42604407 -111988435 -111988435 -178705934 -111988435 -111988435 -111988435 -111988435 -111988435 -111988435 -111988435 -111988435 -42604407 -42604407 -42604407 -42604407 -3697606 -42604407 -42604407 -111988435 -42604407 -42604407 -42604407 -42604407 -3697606 -3697606 -3697606 -3697606 -3697606 -3697606 34213743 34213743 34213743 -3697606 -3697606 -3697606 34213743 34213743 64055282 34213743 64055282 34213743 64055282 34213743 34213743 -3697606 34213743 -3697606 -3697606 -3697606 34213743 34213743 34213743 -3697606 -3697606…

Example 3:

Input: 3736 400221055 -614119752 -897924279 -364006949 206060580 730428783 834011086 247148345 -156037167 -161576011 -812761693 546001075 425591912 764602576 274457890 -29416749 -977414881 327988856 596014431 -261792541 549482849 -880265538 612476425 706591649 579740829 42763876 210733731 -193493015 -689162588 948652339 -465199470 -395835138 -162645022 842178579 -241422990 638197353 422147038 64758785 -14064888 527696136 641532535 774270742 -370746474 237618751 -822456698 -15516520 456088476 -486092105 551349344 966600426 246033151 790692808 681837245 94717179 236353804 615652060 -712273152 -856667239 967471306 274760859 -252064960 555951710 -68707234 156059487 -164324369 -948113442 -31067688 -274356035 -772653868 207739971 -148297777 961961851 -749654346 398102426 174933232 535302374 -44208942 8…
Output: 400221055 -614119752 -614119752 -614119752 -364006949 -364006949 206060580 206060580 206060580 -156037167 -156037167 -156037167 206060580 206060580 247148345 206060580 206060580 206060580 247148345 206060580 247148345 206060580 247148345 247148345 274457890 247148345 247148345 210733731 210733731 210733731 210733731 206060580 206060580 206060580 206060580 206060580 210733731 206060580 206060580 206060580 210733731 210733731 210733731 210733731 210733731 206060580 210733731 206060580 210733731 210733731 237618751 237618751 246033151 237618751 237618751 237618751 237618751 236353804 237618751 237618751 237618751 237618751 237618751 236353804 236353804 210733731 210733731 206060580 206060580 206060580 206060580 206060580 206060580 206060580 206060580 206060580 206060580 206060580 206060580 20…

Constraints:

1 <= n <= 4000; -10^9 <= a[i] <= 10^9.

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