CT61728

Paige Counts the ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Every season at the lantern lake of Firefly Mere, someone must file the annual report. This year the task falls to Paige, armed only with the ledgers register. 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: 544 -171888330 970891094 446607949 327732993 -325242600 -739173552 377888461 -509164487 -448851525 -416173755 -24268397 -727005722 866853938 -325705228 275172085 396720292 -206816045 -727816821 -605896502 -392384993 -764475532 247553676 -11513551 -436098733 263031619 834770496 192610518 225351030 812316591 -478768728 -573128811 773958661 -227721288 -929119987 -381658185 736172575 680350961 211343918 366164267 244563861 353649885 733597459 -418057197 -618352579 900518236 162695675 -907975419 418265732 407985773 -644631018 571910634 -400887698 -556878609 750791494 989372307 -411098675 -679485830 157824256 352186771 14761680 830525622 933511214 738437997 -220054874 -414163877 928720797 -575758104 216395863 -225516833 736017237 -282439337 638542104 131635726 621904329 648637107 -923803210 5293…
Output: -171888330 -171888330 446607949 327732993 327732993 -171888330 327732993 -171888330 -171888330 -325242600 -171888330 -325242600 -171888330 -325242600 -171888330 -171888330 -171888330 -206816045 -206816045 -325242600 -325242600 -325242600 -206816045 -325242600 -206816045 -206816045 -171888330 -171888330 -24268397 -171888330 -171888330 -171888330 -171888330 -206816045 -206816045 -206816045 -171888330 -171888330 -24268397 -24268397 -11513551 -11513551 -11513551 -24268397 -11513551 -11513551 -11513551 -11513551 162695675 -11513551 162695675 -11513551 -11513551 -11513551 162695675 -11513551 -11513551 -11513551 157824256 14761680 157824256 157824256 162695675 157824256 157824256 157824256 157824256 157824256 157824256 157824256 157824256 157824256 157824256 157824256 162695675 157824256 15782425…

Example 2:

Input: 3401 310544771 417425036 621877320 -237584231 -689509596 -449458848 972291020 -365692487 344870941 360019367 -666115936 -570602870 -301238303 60538384 -572126292 253508916 808527121 -451178521 -624502132 -865374238 458963325 936790108 -562370229 -949782660 -8110066 -13233517 558598066 -299673943 -361755850 -243695812 -313585533 25844152 384820869 -913877151 408815723 -701400110 829102440 820543723 972580653 -442870068 269630751 695967429 -749494158 251448859 548970955 -33319695 222056762 -381946394 -24572695 -693703754 -21595238 -308075679 -506635348 -344443474 465922440 -141613581 -389883834 -91958058 -385907101 -332772106 418597692 -13297084 -793645576 -414078196 -294021389 -334158572 193986011 185490568 -642622767 5038499 228109106 870553487 -34744076 -629162787 -425442661 -622064669 -7…
Output: 310544771 310544771 417425036 310544771 310544771 -237584231 310544771 -237584231 310544771 310544771 310544771 -237584231 -237584231 -237584231 -237584231 -237584231 60538384 -237584231 -237584231 -301238303 -237584231 -237584231 -237584231 -301238303 -237584231 -237584231 -13233517 -237584231 -237584231 -243695812 -243695812 -243695812 -237584231 -243695812 -237584231 -243695812 -237584231 -237584231 -13233517 -237584231 -13233517 -13233517 -13233517 -13233517 -8110066 -13233517 -8110066 -13233517 -13233517 -24572695 -21595238 -24572695 -24572695 -33319695 -24572695 -33319695 -33319695 -91958058 -91958058 -141613581 -91958058 -91958058 -91958058 -141613581 -141613581 -237584231 -141613581 -141613581 -141613581 -141613581 -91958058 -91958058 -34744076 -91958058 -91958058 -141613581 -14161…

Example 3:

Input: 3612 -275357999 84434284 -942040874 663115963 982982648 899199965 850309654 -213689981 765456784 -177912925 -853660217 718227514 -938551683 513870618 -850555590 629782813 -231040451 261360643 -590045112 -678127867 -516760133 -365982329 -8126311 -493270057 -725309978 339865327 -566161936 -798742402 506887410 579952896 -13744338 337961048 839504931 -157470879 -112522091 707542465 769058306 121131771 -60390614 -462538990 927251317 -996652138 269333530 444180578 42599167 -630315526 827203450 -747914651 -283749700 35216832 -962312403 918045347 -662344127 362311504 449833115 576048132 207236361 -958550878 290818821 -626582248 -234584454 771807550 -29069092 -310452026 333130943 541811794 836866919 -410622131 -866189537 -348114135 469476169 -526707725 -830602851 688565771 628966588 -508872969 -811…
Output: -275357999 -275357999 -275357999 -275357999 84434284 84434284 663115963 84434284 663115963 84434284 84434284 84434284 84434284 84434284 84434284 84434284 84434284 84434284 84434284 -177912925 -177912925 -213689981 -177912925 -213689981 -213689981 -213689981 -213689981 -231040451 -213689981 -213689981 -177912925 -177912925 -13744338 -157470879 -112522091 -112522091 -13744338 -13744338 -13744338 -60390614 -13744338 -60390614 -13744338 -13744338 -8126311 -13744338 -8126311 -13744338 -13744338 -13744338 -13744338 -13744338 -13744338 -13744338 -8126311 -8126311 35216832 -8126311 35216832 -8126311 -8126311 -8126311 -8126311 -13744338 -8126311 -8126311 35216832 -8126311 -8126311 -13744338 -8126311 -13744338 -13744338 -13744338 -8126311 -13744338 -13744338 -29069092 -13744338 -13744338 -13744338 -…

Constraints:

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

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