No.1982 [Cherry 4th Tune B] 絶険
レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 50
作問者 : 👑 Kazun / テスター : akakimidori 👑 potato167
タグ : / 解いたユーザー数 50
作問者 : 👑 Kazun / テスター : akakimidori 👑 potato167
問題文最終更新日: 2022-06-17 20:22:44
問題文
$N$ 個の連続する区画が1列に並んでおり, これらは左から順に区画 $1$, 区画 $2$, $\dots$, 区画 $N$ と名付けられている. また, この $N$ 個の区画の地面は水平である.
最初, 全ての区画の壁の高さは $0$ である.
$k=1,2, \dots, K$ の順に以下の操作を行う.
- $L_k \leq i \leq R_k$ を満たす全ての整数 $i$ に対して, 区画 $i$ にその時点で建てられている壁の上に新たに高さ $H_k$, 色 $C_k$ の壁を建てる.
全ての操作を終えた $N$ 個の区画の壁に対して, 次の $Q$ 個の質問に答えよ. ただし, $q~(1 \leq q \leq Q)$ 番目の質問は $2$ つの整数 $I_q, X_q$ で与えられる.
- 区画 $I_q$ において, 地面から高さ $(X_q-0.5)$ 地点の壁の色を答えよ. ただし, その高さに壁がない場合はその旨を報告せよ.
なお, 壁はいくらでも高く建てることができるものとし, 途中で壁が崩落したり, 変形, 変色しないものとする.
制約
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq K \leq 2 \times 10^5$
- $1 \leq Q \leq 2 \times 10^5$
- $1 \leq L_k \leq R_k \leq N$
- $1 \leq C_k \leq 2 \times 10^5$
- $1 \leq H_k \leq 10^9$
- $1 \leq I_q \leq N$
- $1 \leq X_q \leq 2 \times 10^{14}$
- 入力は全て整数である.
入力
$N$ $K$ $Q$ $L_1$ $R_1$ $C_1$ $H_1$ $\vdots$ $L_K$ $R_K$ $C_K$ $H_K$ $I_1$ $X_1$ $\vdots$ $I_Q$ $X_Q$
出力
出力は $Q$ 行からなる. 第 $q~(1 \leq q \leq Q)$ 行目には, 区画 $I_q$ にある高さ $(X_q-0.5)$ 地点の壁の色を整数で答えよ.
ただし, その地点に壁が存在しない場合は代わりに -1
を出力せよ.
最後に改行を忘れないこと.
サンプル
サンプル1
入力
6 4 3 1 3 1 1 2 4 2 2 4 4 1 3 1 5 5 2 2 3 4 10 5 2
出力
2 -1 5
壁の状況は以下のようになっている.
- 最初の質問は区画 $2$ における地面から高さ $3-0.5=2.5$ 地点の色である. これは $2$ が答えである.
- 2番目の質問は区画 $4$ における地面から高さ $10-0.5=9.5$ 地点の色であるが, そもそもそこに壁はない. よって,
-1
と出力しなければならない.
サンプル2
入力
46 0 1 46 46
出力
-1
$1$ 回も操作していないので, 全ての区画に壁はない.
サンプル3
入力
200000 5 4 111 1111 1 11111 2 22222 22 2222222 33333 33333 333 333 44 44444 4444 44444444 555 55555 55555 555 66 6666 777 7777 88888 888 99 9999999
出力
22 1 -1 4444
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。