CT61778

Aria's Beryl marks

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Aria the inventory keeper watches over the temple city of Sunspire's stores of marks. A careful computation stands between order and chaos. 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: 3471 -539003287 489877435 -307267992 466714680 801733785 661005240 357708784 -432043535 727554464 610713090 -96352295 -797214280 -541269379 -270604214 423868861 -842292804 -149639485 -95161808 -405822060 606556397 226207688 592940800 843105818 486056195 197276325 324082038 -3087842 -274453996 -845806557 635000773 197615967 -911484714 -657641824 -356027137 -501962412 -998645051 442618763 -731550842 -863677350 800839214 -908922306 805431909 -673254887 379401617 -421431115 234133010 300395135 -569373390 -274176874 270814974 31499482 969963162 311797945 626604912 868926775 -64726461 729630159 569106285 490626266 -254202525 -361202503 60249395 -52535925 996882010 -780742841 246486381 397845136 710775342 -675222432 79712737 927722936 -922272817 -935049211 -766949894 -276146075 -242223465 -112593…
Output: -539003287 -539003287 -307267992 -307267992 466714680 466714680 466714680 357708784 466714680 466714680 466714680 357708784 357708784 -96352295 357708784 -96352295 -96352295 -96352295 -96352295 -96352295 -95161808 -95161808 226207688 226207688 226207688 226207688 226207688 197276325 197276325 197276325 197615967 197276325 197276325 -3087842 -3087842 -95161808 -3087842 -95161808 -95161808 -95161808 -95161808 -95161808 -95161808 -95161808 -95161808 -95161808 -3087842 -95161808 -95161808 -95161808 -3087842 -3087842 31499482 31499482 197276325 31499482 197276325 197276325 197615967 197276325 197276325 60249395 60249395 60249395 60249395 60249395 197276325 197276325 197276325 79712737 197276325 79712737 79712737 60249395 60249395 31499482 31499482 -3087842 -3087842 -3087842 4471702 -3087842 -30…

Example 2:

Input: 3252 -943297271 356039562 224482912 54435589 578062521 403402654 -64359164 501858250 389786413 -583611273 27678014 -487282243 295790955 432245598 980523049 -199072124 -349333871 926644847 -462689545 -660189236 161850814 -967767869 -830140738 -505631013 984351210 577534947 977257037 511960167 531183547 -345084832 945076299 563823534 -249037868 -222157106 -56527980 918974513 -938827489 861045203 -144143811 -954470008 217036688 -906391826 -363275030 -609617229 -657714748 338432111 -137530517 658921055 742962242 801291953 -910653921 317101542 -905116783 -550307388 -919761167 -25494274 950477841 198186709 121195646 796207017 -991574462 19065193 778779695 983313001 -178865358 208576985 -274205144 13222425 869709040 862634222 -70362230 353772217 484689417 896249874 853014962 699609830 891770133 -…
Output: -943297271 -943297271 224482912 54435589 224482912 224482912 224482912 224482912 356039562 224482912 224482912 54435589 224482912 224482912 295790955 224482912 224482912 224482912 224482912 54435589 161850814 54435589 54435589 27678014 54435589 54435589 161850814 161850814 224482912 161850814 224482912 224482912 224482912 161850814 161850814 161850814 161850814 161850814 161850814 54435589 161850814 54435589 54435589 27678014 27678014 27678014 27678014 27678014 54435589 54435589 54435589 54435589 54435589 27678014 27678014 -25494274 27678014 27678014 54435589 54435589 54435589 27678014 54435589 54435589 54435589 54435589 54435589 27678014 54435589 54435589 54435589 54435589 121195646 121195646 161850814 161850814 198186709 161850814 161850814 121195646 161850814 161850814 161850814 1211956…

Example 3:

Input: 3335 -496103293 9790025 678310637 -565117608 -527082119 -612818944 -545722357 -670333899 146368073 -313883289 538874559 -130435619 164968262 -356286525 795978562 -938895639 780951091 -56929232 -107508238 -837592236 402210249 681515943 988107711 -902983558 122887013 541476681 -285251865 254983815 882544141 -384740573 830083959 -897824760 269231932 983632621 305161825 -41996435 -198078721 133246250 977264880 -583941231 -193356276 222667270 -830459974 293218755 807483444 -431977640 790286014 902049577 -968698626 250998840 -402092535 870392476 268798374 131875383 690961999 -602089565 -152002348 -132726527 178840389 127698692 -790921416 641202295 -799112538 507351546 -291891167 -882217887 -606983527 64367322 -655430066 -631461730 -875645081 -274969309 926469048 223082339 468848262 -514828507 29…
Output: -496103293 -496103293 9790025 -496103293 -496103293 -527082119 -527082119 -545722357 -527082119 -527082119 -496103293 -496103293 -313883289 -356286525 -313883289 -356286525 -313883289 -313883289 -130435619 -313883289 -130435619 -130435619 -107508238 -130435619 -107508238 -107508238 -107508238 -107508238 -56929232 -107508238 -56929232 -107508238 -56929232 -56929232 9790025 -41996435 -41996435 -41996435 9790025 -41996435 -41996435 -41996435 -41996435 -41996435 9790025 -41996435 9790025 9790025 9790025 9790025 9790025 9790025 122887013 122887013 131875383 122887013 122887013 9790025 122887013 122887013 122887013 122887013 122887013 122887013 122887013 9790025 9790025 9790025 9790025 -41996435 -41996435 -56929232 -41996435 -41996435 9790025 -41996435 9790025 -41996435 9790025 9790025 64367322 …

Constraints:

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

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