102174: [AtCoder]ABC217 E - Sorting Queries
Description
Score : $500$ points
Problem Statement
We have an empty sequence $A$. You will be given $Q$ queries, which should be processed in the order they are given. Each query is of one of the three kinds below:
1 x
: Append $x$ to the end of $A$.2
: Print the element at the beginning of $A$. Then, delete that element. It is guaranteed that $A$ will not empty when this query is given.3
: Sort $A$ in ascending order.
Constraints
- $1 \leq Q \leq 2 \times 10^5$
- $0 \leq x \leq 10^9$
- $A$ will not be empty when a query
2
is given. - All values in input are integers.
Input
Input is given from Standard Input in the following format:
$Q$ $\mathrm{query} 1$ $\mathrm{query} 2$ $\vdots$ $\mathrm{query} Q$
The $i$-th query, $\mathrm{query} i$, begins with the kind of query $c_i$ ($1$, $2$, or $3$). If $c_i = 1$, the line additionally has an integer $x$.
In other words, each query is in one of the three formats below.
$1$ $x$
$2$
$3$
Output
Print $q$ lines, where $q$ is the number of queries with $c_i = 2$.
The $j$-th line $(1 \leq j \leq q)$ should contain the response for the $j$-th such query.
Sample Input 1
8 1 4 1 3 1 2 1 1 3 2 1 0 2
Sample Output 1
1 2
The $i$-th line below shows the contents of $A$ after the $i$-th query is processed in Sample Input $1$.
- $(4)$
- $(4, 3)$
- $(4, 3, 2)$
- $(4, 3, 2, 1)$
- $(1, 2, 3, 4)$
- $(2, 3, 4)$
- $(2, 3, 4, 0)$
- $(3, 4, 0)$
Sample Input 2
9 1 5 1 5 1 3 2 3 2 1 6 3 2
Sample Output 2
5 3 5
The $i$-th line below shows the contents of $A$ after the $i$-th query is processed in Sample Input $2$.
- $(5)$
- $(5, 5)$
- $(5, 5, 3)$
- $(5, 3)$
- $(3, 5)$
- $(5)$
- $(5, 6)$
- $(5, 6)$
- $(6)$
Input
题意翻译
维护一个空序列 $A$ ,有 $Q$ 次查询: 1. 在 $A$ 的最后插入一个元素一个元素 $x$ 2. 输出 $A$ 的第一个元素并删除这个元素 3. 将这个序列排序Output
分数:$500$分
问题描述
我们有一个空序列$A$。你将得到$Q$个查询,它们应该按照给出的顺序进行处理。 每个查询是以下三种类型之一:
1 x
:将$x$添加到$A$的末尾。2
:打印$A$开头的元素。然后删除该元素。保证在给出此查询时$A$不会为空。3
:将$A$按升序排序。
约束
- $1 \leq Q \leq 2 \times 10^5$
- $0 \leq x \leq 10^9$
- 当给出查询
2
时,$A$不会为空。 - 输入中的所有值都是整数。
输入
输入从标准输入以以下格式给出:
$Q$ $\mathrm{query} 1$ $\mathrm{query} 2$ $\vdots$ $\mathrm{query} Q$
第$i$个查询$\mathrm{query} i$以查询类型$c_i$($1$、$2$或$3$)开头。 如果$c_i = 1$,该行还包含一个整数$x$。
换句话说,每个查询是以下三种格式之一。
$1$ $x$
$2$
$3$
输出
打印$q$行,其中$q$是查询$c_i = 2$的次数。
第$j$行($1 \leq j \leq q$)应包含对第$j$个此类查询的响应。
样例输入 1
8 1 4 1 3 1 2 1 1 3 2 1 0 2
样例输出 1
1 2
在样例输入$1$中处理第$i$个查询后,$A$的内容如下所示。
- $(4)$
- $(4, 3)$
- $(4, 3, 2)$
- $(4, 3, 2, 1)$
- $(1, 2, 3, 4)$
- $(2, 3, 4)$
- $(2, 3, 4, 0)$
- $(3, 4, 0)$
样例输入 2
9 1 5 1 5 1 3 2 3 2 1 6 3 2
样例输出 2
5 3 5
在样例输入$2$中处理第$i$个查询后,$A$的内容如下所示。
- $(5)$
- $(5, 5)$
- $(5, 5, 3)$
- $(5, 3)$
- $(3, 5)$
- $(5)$
- $(5, 6)$
- $(5, 6)$
- $(6)$