問題一覧 > 通常問題

No.1982 [Cherry 4th Tune B] 絶険

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 50
作問者 : 👑 KazunKazun / テスター : akakimidoriakakimidori 👑 potato167potato167
3 ProblemId : 4531 / 出題時の順位表 / 自分の提出
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。