CT64408

Last marks of Tarun

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Morning light hits the salmon ladder of Rushing Falls as Tarun unrolls the day's manifest of marks. The tally will decide the next shipment. 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: 573 900948200 21721381 -674618315 942628584 112571053 850341937 536536017 -20064999 288523503 -621143683 -370972623 368438216 -637250623 56304099 356041195 -713426271 -728733850 -128547198 -138043089 671883944 723489233 -354403651 728234557 707047453 584986885 802485699 179615202 -946417446 -600068251 759225503 -271602347 -859154399 -661530024 -335242352 744114795 -643531814 -660987004 926697257 212967913 978372656 49714952 -915428767 359855723 -46850135 -282425022 -811564677 -23278243 -587895588 -719067434 -681618870 128283352 -693334498 -219518572 -43707443 785354786 547818217 426334478 -400605460 -637041856 944715203 -300600294 -908831490 -394454454 -322619542 323996444 414629855 682637225 -821832035 677016618 713144076 786622093 -345643880 150320542 602252172 -209429030 507018885 43773…
Output: 900948200 21721381 21721381 21721381 112571053 112571053 536536017 112571053 288523503 112571053 112571053 112571053 112571053 56304099 112571053 56304099 56304099 21721381 21721381 21721381 56304099 21721381 56304099 56304099 112571053 112571053 179615202 112571053 112571053 112571053 112571053 56304099 56304099 21721381 56304099 21721381 21721381 21721381 56304099 56304099 56304099 49714952 56304099 49714952 49714952 21721381 21721381 -20064999 -20064999 -23278243 -20064999 -23278243 -23278243 -43707443 -23278243 -23278243 -20064999 -23278243 -23278243 -23278243 -23278243 -43707443 -43707443 -46850135 -43707443 -43707443 -23278243 -43707443 -23278243 -23278243 -20064999 -23278243 -20064999 -20064999 -20064999 -20064999 21721381 -20064999 21721381 21721381 21721381 21721381 21721381 21721…

Example 2:

Input: 3036 62550013 -59998260 929578052 -488087813 899670410 -925749355 368775668 332576761 -964968576 968304578 -404644655 534833038 -283570267 319455578 112792844 -693335517 -587569243 782133478 32318174 -145784257 -715852978 802613806 -504826044 330722797 201204759 -527289073 821045095 554619813 159556616 824203924 -277505100 -474815432 -716221870 -245844992 -543783855 -921453733 764841552 273017877 237718664 -827875377 923290845 105739180 159744783 -799289194 -272207048 223865246 -423017597 353267075 714864486 80280187 -723161277 706818444 -817765640 911014651 80001932 -228740633 534650015 -300249856 852536534 -996662255 -868474145 -141346732 422623015 -925751507 -601002080 -449740654 -198123037 -884952730 -581234412 793372027 785117818 179257374 8265119 -816369083 935209605 839304390 169886…
Output: 62550013 -59998260 62550013 -59998260 62550013 -59998260 62550013 62550013 62550013 62550013 62550013 62550013 62550013 62550013 112792844 62550013 62550013 62550013 62550013 32318174 32318174 32318174 32318174 32318174 62550013 32318174 62550013 62550013 112792844 112792844 112792844 62550013 62550013 32318174 32318174 -59998260 32318174 32318174 62550013 32318174 62550013 62550013 105739180 62550013 62550013 62550013 62550013 62550013 105739180 80280187 80280187 80280187 80280187 80280187 80280187 80001932 80280187 80001932 80280187 80001932 80001932 62550013 80001932 62550013 62550013 32318174 32318174 -59998260 -59998260 -59998260 32318174 32318174 32318174 8265119 32318174 32318174 62550013 62550013 62550013 32318174 62550013 32318174 62550013 62550013 62550013 32318174 32318174 82651…

Example 3:

Input: 3461 61010416 49583676 -666499743 461507055 101906064 706725363 -799398828 -998693908 723677343 895296855 -257060281 -598945882 64248341 267931774 -553014607 -765393180 -836727052 -6102947 109294933 -106799302 515025619 -74888693 643280375 -752328023 523626735 350736105 557788360 391003613 -725353329 212038132 388346908 874090382 -407131437 -330770895 885403611 -344814165 -636669691 -781057403 178183411 -564733799 771906857 -425882207 53252227 -437435597 65030495 520880385 -46021692 -819215798 -939848858 -550987112 327993409 508422769 -807335840 414023673 -145900874 797146324 5073319 -96254947 890205275 -726693261 -499080290 593829222 -857282512 467088275 123261860 -660911529 523507180 392410649 71015878 -737646712 -886081747 -437382123 606238155 977070826 -66007427 -733869505 -188965502 3…
Output: 61010416 49583676 49583676 49583676 61010416 61010416 61010416 49583676 61010416 61010416 61010416 49583676 61010416 61010416 61010416 49583676 49583676 -6102947 49583676 -6102947 49583676 -6102947 49583676 -6102947 49583676 49583676 61010416 61010416 61010416 61010416 64248341 64248341 64248341 61010416 64248341 61010416 61010416 49583676 61010416 49583676 61010416 49583676 53252227 49583676 53252227 53252227 53252227 49583676 49583676 -6102947 49583676 49583676 49583676 49583676 49583676 49583676 49583676 5073319 49583676 5073319 5073319 5073319 5073319 5073319 49583676 5073319 49583676 49583676 53252227 49583676 49583676 5073319 49583676 49583676 49583676 5073319 5073319 5073319 49583676 49583676 49583676 49583676 49583676 5073319 49583676 5073319 49583676 49583676 53252227 49583676 532…

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Last marks of Tarun - MEDIUM Coding Problem | CodeTikki