Median of Queue

Median of Queue

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

现有一个初始时为空的队列,对其进行\(K\)次操作。操作共有3类:
push \(\phantom{x} x\):将整数\(x\)添加到队列的末尾;
pop:将队列头部的元素弹出(如果有的话);
median:输出队列中所有元素的中位数。如果此时队列中元素个数\(n\)为偶数,则规定中位数为第\(n/2\)小的数。
输入\(K\)次操作并依次执行,按照“输出格式”部分的要求输出每次操作的结果。

输入格式

第一行是一个正整数\(K\),表示操作次数;
之后\(K\)行,每行先是1个字符串,表示操作类型,该字符串只可能是pushpopmedian中的某一个;如果是push操作,则之后还有一个整数\(x\),表示添加到队列末尾的数;否则后面没有其他内容。

输出格式

依次执行每个操作并按照如下要求输出结果,每次输出一行:
对于push操作,输出Size = x,其中x用操作后队列中的元素个数代替,=前后各有一个空格;
对于pop操作,如果操作前队列为空,则输出Empty!,否则输出Popped = x,其中x用此次弹出队列的值代替;
对于median操作,如果此时队列为空则输出Empty!,否则输出Median = x,其中x用此时队列内的中位数代替。

样例

输入

12
push 1
push 2
push 4
median
pop
pop
push -3
median
pop
pop
pop
median

输出

Size = 1
Size = 2
Size = 3
Median = 2
Popped = 1
Popped = 2
Size = 2
Median = -3
Popped = 4
Popped = -3
Empty!
Empty!

数据范围及约定

50%的数据:\(K \le 1000\);
100%的数据:\(K \le 10^5\), 每次push操作插入的数均在闭区间\([-10^5, 10^5]\)内。
时间限制1s,空间限制64MB。

2019.2.1补题通道

未参加
状态
已结束
规则
ACM/ICPC
题目
3
开始于
2019-02-01 17:30
结束于
2019-02-10 00:00
持续时间
198.5 小时
主持人
参赛人数
24