CT60568

The Middle So Far of the Frosted ledgers

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Arjun runs the signal tower at the anvil district of Hammerfall. Today the books show a list of ledgers, 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: 687 79653903 -67544419 -18079855 -956752433 594217856 502199977 -695538643 -276760755 743739387 -760585985 -128758061 368325328 476534670 -979768081 -863048379 450227162 243807164 188109732 -168923629 -134904642 420387671 -195153261 821504676 -215411875 -91535773 -942236059 496304074 -475756514 31116777 147124693 -482183996 -830927400 301262836 642986236 -872147620 674054457 -791768920 171437997 -244054781 475946138 -601772428 912750699 -524811329 -582670009 -637754638 -822747114 -777398631 626217952 -401689828 76775886 -826644821 874508709 228732151 -364817770 752143895 -761554312 268864908 -281502777 -891526687 -989391972 -208979188 772213176 -482917184 -130152252 49428703 -846496338 -921351788 -704955292 -498465117 779277958 -923376757 -957587111 -949550828 934072438 449213379 -61931079…
Output: 79653903 -67544419 -18079855 -67544419 -18079855 -18079855 -18079855 -67544419 -18079855 -67544419 -67544419 -67544419 -18079855 -67544419 -67544419 -67544419 -18079855 -18079855 -18079855 -67544419 -18079855 -67544419 -18079855 -67544419 -67544419 -91535773 -67544419 -91535773 -67544419 -67544419 -67544419 -91535773 -67544419 -67544419 -67544419 -67544419 -67544419 -67544419 -67544419 -67544419 -67544419 -67544419 -67544419 -91535773 -91535773 -128758061 -128758061 -128758061 -128758061 -128758061 -128758061 -128758061 -91535773 -128758061 -91535773 -128758061 -91535773 -128758061 -128758061 -134904642 -134904642 -134904642 -134904642 -134904642 -130152252 -134904642 -134904642 -168923629 -168923629 -168923629 -168923629 -195153261 -195153261 -195153261 -168923629 -195153261 -195153261 -2…

Example 2:

Input: 956 449852462 617203610 81945508 -643404322 -395109424 737523319 -51905811 480108297 825761792 544136956 799010452 -156924384 911001401 168440190 -21647030 664319529 134227142 280028439 -167604733 153015933 -499342469 -269253319 -709397301 -711905490 538291609 490219909 -515126837 -250379499 928672995 433868338 -689332243 312246193 171787235 -137400161 -289462013 432811335 -411537244 -854064407 302013500 570614095 779336188 -329951897 -583449875 974205406 271317576 23466165 648500231 -524584895 -488401256 576063181 -51779953 530601543 -590733797 588159748 -165337276 141393756 805385974 577968638 -352894673 -817857340 512733428 -395400259 951278234 110183341 -371310698 914598229 326975412 217159503 759528757 554754199 351227046 373170927 -250916103 551965912 772268819 364062470 12264606 864…
Output: 449852462 449852462 449852462 81945508 81945508 81945508 81945508 81945508 449852462 449852462 480108297 449852462 480108297 449852462 449852462 449852462 449852462 280028439 280028439 168440190 168440190 153015933 153015933 134227142 153015933 153015933 153015933 134227142 153015933 153015933 153015933 153015933 168440190 153015933 153015933 153015933 153015933 134227142 153015933 153015933 168440190 153015933 153015933 153015933 168440190 153015933 168440190 153015933 153015933 153015933 153015933 153015933 153015933 153015933 153015933 141393756 153015933 153015933 153015933 141393756 153015933 141393756 153015933 141393756 141393756 141393756 153015933 153015933 168440190 168440190 171787235 171787235 171787235 171787235 217159503 217159503 217159503 217159503 217159503 171787235 21715…

Example 3:

Input: 180 863204215 515381381 62206272 -740786127 -710127630 921426673 316873313 -498326553 -945839292 -463123878 244458330 -512352696 790977115 -39633562 -663554282 731832711 -899173182 -957435590 5650537 196704301 463022956 180226730 -718407285 536254300 807596163 -290950887 -4661262 239838139 723019907 138331521 289081610 -722888117 -89262802 150119601 492450667 886298854 450904666 -139371837 -725785403 869236791 -420350622 -389310164 625396699 -992568884 -62775076 -151237088 682163528 -965910473 -392834362 994787539 674554538 854181136 283314699 937311492 -127112446 77137280 -399508140 280931161 -604743857 -116650905 -17623614 -202354040 -635344022 56764669 -782201095 -429903505 -390335479 -67741859 683296262 -695936953 418925129 -172466685 997340312 -692146017 -335687665 -358563617 12581405…
Output: 863204215 515381381 515381381 62206272 62206272 62206272 316873313 62206272 62206272 -463123878 62206272 -463123878 62206272 -39633562 -39633562 -39633562 -39633562 -463123878 -39633562 -39633562 5650537 5650537 5650537 5650537 62206272 5650537 5650537 5650537 62206272 62206272 138331521 62206272 62206272 62206272 138331521 138331521 150119601 138331521 138331521 138331521 138331521 62206272 138331521 62206272 62206272 5650537 62206272 5650537 5650537 5650537 62206272 62206272 138331521 138331521 138331521 77137280 77137280 77137280 77137280 62206272 62206272 5650537 5650537 5650537 5650537 -4661262 -4661262 -17623614 -4661262 -17623614 -4661262 -17623614 -4661262 -17623614 -17623614 -39633562 -17623614 -17623614 -17623614 -39633562 -17623614 -39633562 -17623614 -17623614 -4661262 -1762361…

Constraints:

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

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