CT59135

The Middle So Far of Balmcrest

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the cedar groves of Balmcrest, Captain records each signals 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: 3639 740518421 885110520 208604392 -879879875 664901850 422485683 -43771687 -499828686 -987504238 106672348 -121134574 -155208219 -425395626 -850665371 462090869 -31462846 -402660418 627194534 -259902741 -938109892 -402081974 -200155976 -795455567 665125791 -815168509 -412246270 755178216 258000632 -797958287 118374064 797068640 -668563756 -347198758 779905109 982002087 946064492 -365844558 467481612 964819530 -194310869 -490212310 -237063538 435329583 -495361367 -924270356 -609654259 80367818 -5474983 180327609 198593087 197764858 810310281 -681455335 -30958879 355281594 543754139 -736127935 635165543 -130811427 367770646 -817474390 694571054 -281559829 -76782676 143005452 70926611 972889627 331880367 419157312 -793042102 -123607056 -567251173 -304044913 -235378750 -863744457 824799330 60…
Output: 740518421 740518421 740518421 208604392 664901850 422485683 422485683 208604392 208604392 106672348 106672348 -43771687 -43771687 -121134574 -43771687 -43771687 -43771687 -43771687 -43771687 -121134574 -121134574 -155208219 -155208219 -155208219 -155208219 -200155976 -155208219 -155208219 -155208219 -155208219 -121134574 -155208219 -155208219 -155208219 -121134574 -121134574 -121134574 -121134574 -43771687 -121134574 -121134574 -155208219 -121134574 -155208219 -155208219 -194310869 -155208219 -155208219 -121134574 -121134574 -43771687 -43771687 -43771687 -43771687 -31462846 -31462846 -31462846 -31462846 -31462846 -31462846 -31462846 -31462846 -31462846 -43771687 -31462846 -31462846 -30958879 -30958879 -5474983 -30958879 -30958879 -31462846 -31462846 -43771687 -43771687 -43771687 -31462846 …

Example 2:

Input: 1196 -128363388 415996686 657533260 506703795 66662765 375729503 -496287153 -427396118 -686088668 -348748156 -464639022 496713734 557837909 -755543950 173876923 -953618389 678542559 -9336200 164985998 552401427 467091923 -609577310 -285516111 -293925735 74993391 -916444434 -980481641 525548769 916958268 904198196 -618603917 -569051208 -163159033 -936119826 56726889 646918643 -388630902 -795346262 -223845500 -962191957 760665713 -101045184 -303232756 -166332608 -607477032 -811475654 417361465 -653761595 -695959886 -356192117 -381454559 787478815 -231796504 381482782 410478137 509017180 621904225 625938204 -180900746 -930929103 772943513 -754147579 864799282 286304546 348127001 -38215074 811853346 -160301446 696473939 -608474966 404076338 -806821890 292061292 902294017 562534956 -613513187 2…
Output: -128363388 -128363388 415996686 415996686 415996686 375729503 375729503 66662765 66662765 -128363388 -128363388 -128363388 66662765 -128363388 66662765 -128363388 66662765 -9336200 66662765 66662765 164985998 66662765 66662765 -9336200 66662765 -9336200 -9336200 -9336200 66662765 66662765 66662765 -9336200 -9336200 -128363388 -9336200 -9336200 -9336200 -128363388 -128363388 -163159033 -128363388 -128363388 -128363388 -163159033 -163159033 -166332608 -163159033 -166332608 -166332608 -223845500 -223845500 -223845500 -223845500 -223845500 -166332608 -166332608 -163159033 -163159033 -163159033 -166332608 -163159033 -166332608 -163159033 -163159033 -128363388 -128363388 -101045184 -128363388 -101045184 -128363388 -101045184 -128363388 -101045184 -101045184 -38215074 -101045184 -38215074 -101045…

Example 3:

Input: 2445 -90487146 883739275 620163862 -943513874 54013839 -958729374 258760697 467207102 -468052332 717739149 971997239 -750268160 549599871 -983427921 -22668011 870726397 309969409 297488689 739841291 732760599 928778415 891962855 -279052905 268852812 -386684772 792808527 -475326126 143951260 -468415981 301214910 978498395 155623463 -625783637 -66510186 32479747 941480281 377245566 198367485 492913459 700133205 -885548861 301683242 -152697371 714968187 -588737558 -915645075 -411791219 -638065889 892774517 -494164251 824903340 249728891 141151 -106476069 952234511 936817343 -522720629 958179316 -674473075 -527393499 934283689 545078001 917034383 -992920294 -499350686 -797913822 -541679288 -946716743 121338019 -500663005 -108552859 204381841 523280051 -635100682 -890665150 -536568739 975708086…
Output: -90487146 -90487146 620163862 -90487146 54013839 -90487146 54013839 54013839 54013839 54013839 258760697 54013839 258760697 54013839 54013839 54013839 258760697 258760697 297488689 297488689 309969409 309969409 309969409 297488689 297488689 297488689 297488689 268852812 268852812 268852812 297488689 268852812 268852812 258760697 258760697 258760697 268852812 258760697 268852812 268852812 268852812 268852812 268852812 268852812 268852812 258760697 258760697 198367485 258760697 198367485 258760697 249728891 249728891 198367485 249728891 249728891 249728891 249728891 249728891 198367485 249728891 249728891 258760697 249728891 249728891 198367485 198367485 155623463 155623463 143951260 143951260 143951260 155623463 143951260 143951260 121338019 143951260 143951260 143951260 121338019 143951260…

Constraints:

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

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