CT62884

The Frostgate Middle So Far

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Devi runs the salt store at the northern keep of Frostgate. Today the books show a list of registers, and the numbers must be worked out before sundown. 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: 1246 -930887770 -590711444 -631653421 -690865644 -225603570 -665938062 -830844772 478706687 605201370 -528372545 -836099908 -827216999 431681077 948607162 825457652 180921018 538854341 371284403 -299770855 -586109041 -755994246 -153240768 -21288235 -842354708 -790952185 -383070917 -244424323 165612459 646155354 -744393173 -632187394 -752090991 -252030144 -900108716 995733113 843513059 -351894075 -916158743 698851593 959127240 -663434718 406410016 -103551387 612869171 -249527114 -912632933 -389698238 -193978472 407874141 827176276 642791161 -889111862 225696548 -603392463 -112283231 897005149 -489007917 713024838 -74290984 832650501 680599064 -970494618 -397812537 603915427 998263523 793985034 276368145 -882008630 -778397445 -453035438 -571351753 153281349 -10560554 84014896 896661535 -9712…
Output: -930887770 -930887770 -631653421 -690865644 -631653421 -665938062 -665938062 -665938062 -631653421 -631653421 -631653421 -665938062 -631653421 -631653421 -590711444 -590711444 -528372545 -528372545 -299770855 -528372545 -528372545 -528372545 -299770855 -528372545 -528372545 -528372545 -383070917 -383070917 -299770855 -383070917 -383070917 -528372545 -383070917 -528372545 -383070917 -383070917 -351894075 -383070917 -351894075 -351894075 -351894075 -351894075 -299770855 -299770855 -252030144 -299770855 -299770855 -299770855 -252030144 -252030144 -249527114 -252030144 -249527114 -252030144 -249527114 -249527114 -249527114 -249527114 -244424323 -244424323 -225603570 -244424323 -244424323 -244424323 -225603570 -225603570 -193978472 -225603570 -225603570 -244424323 -244424323 -244424323 -2256035…

Example 2:

Input: 442 -151814363 822638690 389434200 -515410247 -82524791 -670943059 155934001 389125514 259377975 332902989 -247660711 -631051196 655484625 257410255 -921801316 -571277278 18022642 95179232 453919475 33975252 -585244637 929756908 262952200 -150138867 661950828 -387828499 248602672 59136360 -263980556 524024868 690815632 -475340201 783365591 -225899749 -8026 149336827 539561654 312815385 -229970951 241658337 390114198 204811044 -782393710 -520672009 922705742 -279461279 347336366 -69717466 617906513 91816176 329075395 -489895973 -873468079 -572077540 214337831 -210164810 395495090 -943366444 -832985660 126517768 201178156 565279801 -859309098 -462252564 263870287 778582191 857535815 -923162673 -395596954 -899977204 -765000055 -26900862 737907414 6793485 50665880 -744500857 573952069 -8561045…
Output: -151814363 -151814363 389434200 -151814363 -82524791 -151814363 -82524791 -82524791 155934001 155934001 155934001 -82524791 155934001 155934001 155934001 -82524791 18022642 18022642 95179232 33975252 33975252 33975252 95179232 33975252 95179232 33975252 95179232 59136360 59136360 59136360 95179232 59136360 95179232 59136360 59136360 59136360 95179232 95179232 95179232 95179232 149336827 149336827 149336827 95179232 149336827 95179232 149336827 95179232 149336827 95179232 149336827 95179232 95179232 91816176 95179232 91816176 95179232 91816176 91816176 91816176 95179232 95179232 95179232 91816176 95179232 95179232 126517768 95179232 95179232 91816176 91816176 59136360 91816176 59136360 59136360 50665880 59136360 50665880 59136360 50665880 50665880 50665880 50665880 33975252 33975252 3397525…

Example 3:

Input: 3463 -307123701 168634451 -905169400 125246328 -605804201 -372581616 -288959547 -245065686 -356702158 -821981271 571125459 -386362554 -490136084 559818967 249747467 413845811 262547799 625053302 -709298658 -744534855 -463386736 -800040905 998780108 991502108 971149691 -969276508 759196531 908801343 557786638 255809728 631632855 198838766 -780556522 492252159 422294630 -394907923 -631291905 527314216 -51313333 -489510274 652995227 -726957749 -830234150 -379522024 -531534196 655730547 -910733503 624610897 147290333 -522215987 29119642 -199707152 -693004571 344276813 369260913 190985345 -838707127 -719888678 -253413233 -8188705 -765792908 199069908 -584516608 336703805 962306914 -806537884 713978848 -590218739 144759582 154752921 -989102120 -179086750 692142720 -794181550 902437583 771677061 …
Output: -307123701 -307123701 -307123701 -307123701 -307123701 -372581616 -307123701 -307123701 -307123701 -356702158 -307123701 -356702158 -356702158 -356702158 -307123701 -307123701 -288959547 -288959547 -288959547 -307123701 -307123701 -356702158 -307123701 -307123701 -288959547 -307123701 -288959547 -288959547 -245065686 -245065686 125246328 125246328 125246328 125246328 168634451 125246328 125246328 125246328 125246328 -51313333 125246328 -51313333 -51313333 -245065686 -245065686 -245065686 -245065686 -245065686 -51313333 -245065686 -51313333 -199707152 -199707152 -199707152 -51313333 -51313333 -51313333 -199707152 -199707152 -199707152 -199707152 -199707152 -199707152 -199707152 -51313333 -199707152 -51313333 -199707152 -51313333 -51313333 -51313333 -179086750 -51313333 -179086750 -51313333 …

Constraints:

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

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