CT58943

The Galeholm Middle So Far

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the zephyr cliffs of Galeholm, June records each ledgers in a worn leather ledger. The guild wants answers, not guesses. 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: 2361 62366395 -129760530 -505968147 -464774982 184354023 -514300889 -104888315 200478199 -31515482 -895655617 -326422957 -180819845 -323955720 -510086974 971981708 362112831 -914666821 -845194089 95928014 641799595 575237299 -820281978 730683303 116909848 498139290 97738032 255318885 319898905 -510904494 -329170535 326328438 135598761 848925304 881364139 376737902 -749371658 774242767 961800342 511701792 -563363352 -829735261 -160269161 617871429 862345876 -590778532 667387751 967364670 -18112759 827580660 -217351452 521550048 -506693897 -135839629 -281458429 198300955 -52696943 -306173685 -508460249 287604052 315210216 126281252 782871756 -427944694 -118866792 101510388 -750322000 -54478840 -449747389 727797789 707940395 -524260850 540842669 581683705 345046505 621845148 -628235087 581789…
Output: 62366395 -129760530 -129760530 -464774982 -129760530 -464774982 -129760530 -129760530 -104888315 -129760530 -129760530 -180819845 -180819845 -323955720 -180819845 -180819845 -180819845 -323955720 -180819845 -180819845 -129760530 -180819845 -129760530 -129760530 -104888315 -104888315 -31515482 -31515482 -31515482 -104888315 -31515482 -31515482 62366395 62366395 95928014 62366395 95928014 95928014 97738032 95928014 95928014 62366395 95928014 95928014 95928014 95928014 97738032 95928014 97738032 95928014 97738032 95928014 95928014 62366395 95928014 62366395 62366395 -18112759 62366395 62366395 95928014 95928014 95928014 62366395 95928014 62366395 62366395 -18112759 62366395 62366395 62366395 62366395 95928014 95928014 97738032 95928014 97738032 95928014 95928014 95928014 95928014 95928014 959…

Example 2:

Input: 2400 -850611541 -230395738 -436451142 779618749 27439378 -359467103 587110617 675034732 -358048897 926003198 -662864699 -64904451 678639515 96227605 235324959 -320555169 -39935133 -935908632 377057968 -234634136 -751237723 -832682229 570836691 599598599 51178481 361171204 805673952 -731024723 29711119 418429295 -230580018 563711709 -375630102 -819731707 -232132756 -975198417 404100552 978924579 -778199466 315613883 75405026 915885128 -945012398 922703830 -31463214 331626982 -63416383 -822783039 837268178 -735541422 433986524 -393189325 780536704 971815287 460324498 -357714685 -951515013 240278076 32687562 -147003619 907150967 454507366 -592121983 -494801934 434132397 -792896749 534484907 883016856 -233830481 707474972 -279584133 410147664 -727511200 -761102615 501640373 702705933 292376332…
Output: -850611541 -850611541 -436451142 -436451142 -230395738 -359467103 -230395738 -230395738 -230395738 -230395738 -230395738 -230395738 -64904451 -64904451 27439378 -64904451 -39935133 -64904451 -39935133 -64904451 -64904451 -230395738 -64904451 -64904451 -39935133 -39935133 27439378 -39935133 27439378 27439378 27439378 27439378 27439378 -39935133 -39935133 -64904451 -39935133 -39935133 -39935133 -39935133 27439378 27439378 27439378 27439378 27439378 27439378 27439378 -31463214 27439378 -31463214 27439378 -31463214 27439378 27439378 29711119 27439378 27439378 27439378 29711119 27439378 29711119 29711119 29711119 27439378 29711119 27439378 29711119 29711119 29711119 29711119 29711119 29711119 29711119 27439378 29711119 29711119 32687562 29711119 32687562 29711119 29711119 29711119 29711119 2743…

Example 3:

Input: 456 991170161 35282296 398973713 -373110298 -890122817 563951500 490893014 -481982155 -147202685 929834897 -936409054 -610077754 109995317 300225922 805249196 -212433302 -222923955 -201965244 -271314563 -134768125 -109401398 827436295 414885350 601499641 -787043604 -769555282 -423843405 376370809 838083267 577847281 -7041777 -998397697 -643606210 808854909 -534101532 -771027956 -858090042 -350240358 -831588739 -726753260 598052 -178711513 -649537696 15089358 -714299060 915561623 -632457504 -779478907 98541864 899266383 -324399924 -403114611 429217191 -315187736 -527291265 -596127169 865686752 -503060262 -730029384 -401319508 -415699194 -604183095 613129753 -912776730 -255990383 522374187 -973614429 47369069 141148377 577252809 608379840 -512590734 -522869152 -132383883 693349678 -240428586…
Output: 991170161 35282296 398973713 35282296 35282296 35282296 398973713 35282296 35282296 35282296 35282296 -147202685 35282296 35282296 109995317 35282296 35282296 -147202685 -147202685 -147202685 -134768125 -134768125 -109401398 -109401398 -109401398 -134768125 -134768125 -134768125 -109401398 -109401398 -7041777 -109401398 -109401398 -109401398 -109401398 -134768125 -134768125 -147202685 -147202685 -201965244 -147202685 -178711513 -178711513 -178711513 -178711513 -178711513 -178711513 -201965244 -178711513 -178711513 -178711513 -201965244 -178711513 -201965244 -201965244 -212433302 -201965244 -212433302 -212433302 -222923955 -222923955 -271314563 -222923955 -271314563 -255990383 -255990383 -255990383 -255990383 -222923955 -222923955 -212433302 -222923955 -222923955 -222923955 -212433302 -2229…

Constraints:

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

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