Persistent Queue

AC一覧

Problem Statement
問題文

Let $S_{-1}$ be an empty sequence. Process the following $Q$ queries. The $i$-th query is given in the following form.

  • 0 $t_i$ $x_i$: Define $S_i$ as the sequence obtained by adding $x_i$ to the end of $S_{t_i}$.
  • 1 $t_i$: Define $S_i$ as the sequence obtained by deleting the front element of $S_{t_i}$. Print the deleted element.

$S_{-1}$ を空の列とします。 $Q$ 個のクエリを処理してください。 $i$ 個目のクエリは以下の形式で与えられます。

  • 0 $t_i$ $x_i$: $S_{t_i}$ の末尾に $x_i$ を追加した列を $S_i$ とする。
  • 1 $t_i$: $S_{t_i}$ の先頭を削除した列を $S_i$ とする。削除した要素を出力する。

Constraints
制約

  • $1 \leq Q \leq 500{,}000$
  • $-1 \leq t_i < i$
  • $0 \leq x_i \leq 10^{9}$
  • In query 1, $S_{t_i}$ is not empty.
  • $1 \leq Q \leq 500{,}000$
  • $-1 \leq t_i < i$
  • $0 \leq x_i \leq 10^{9}$
  • クエリ 1 について、$S_{t_i}$ は空ではない。

Input
入力

$Q$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q-1}$

Sample
サンプル

# 1

6
0 -1 6
0 0 7
1 0
0 -1 8
1 3
1 1
6
8
6

Forum


Timelimit: 5 secs

Before submitting, please confirm terms and conditions