E - Sorting Queries

Contest Duration: 2021-09-04(Sat) 12:00 - 2021-09-04(Sat) 13:40 (local time) (100 minutes) Back to Home

E - Sorting Queries Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $500$ 点

問題文

空の列 $A$ があります。クエリが $Q$ 個与えられるので、与えられた順番に処理してください。
クエリは次の $3$ 種類のいずれかです。

1 x : $A$ の最後尾に $x$ を追加する。
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$ が追加で与えられる。

すなわち、各クエリは以下に示す $3$ つの形式のいずれかである。

 $1$   $x$

$2$

$3$

出力

$c_i = 2$ を満たすクエリの回数を $q$ として $q$ 行出力せよ。
$j$ $(1 \leq j \leq q)$ 行目では $j$ 番目のそのようなクエリに対する答えを出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

1
2

入力例 $1$ において、 $i$ 番目のクエリを処理した後の $A$ の状態を $i$ 行目に示すと以下のようになります。

$(4)$
$(4, 3)$
$(4, 3, 2)$
$(4, 3, 2, 1)$
$(1, 2, 3, 4)$
$(2, 3, 4)$
$(2, 3, 4, 0)$
$(3, 4, 0)$

入力例 2Copy

Copy

出力例 2Copy

Copy

5
3
5

入力例 $2$ において、 $i$ 番目のクエリを処理した後の $A$ の状態を $i$ 行目に示すと以下のようになります。

$(5)$
$(5, 5)$
$(5, 5, 3)$
$(5, 3)$
$(3, 5)$
$(5)$
$(5, 6)$
$(5, 6)$
$(6)$

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 1Copy

Copy

Sample Output 1Copy

Copy

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 2Copy

Copy

Sample Output 2Copy

Copy

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)$