Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 100 点
問題文
JOI 市には 1 本の十分に長い道路がある.この道路は数直線とみなすことができ,各地点は 1 個の実数による座標で表される.
また,JOI 市にはこの道路に沿って N 個の鐘があり,座標の小さい順に 1 から N までの番号が付けられている.鐘 i (1 ≦ i ≦ N) は座標 A_i にある.
JOI 市では,1 年の終わりにこれらの鐘を一斉に鳴らすのが一大イベントとなっている.
どの鐘も,鳴らすとその鐘と同じ地点では強さ K の音で聞こえるが,距離が 1 離れるごとに聞こえる音の強さは 1 小さくなり,距離が K 以上離れると 0 になる.すなわち,鐘 i を鳴らしたとき,座標 x で聞こえる鐘 i の音の強さは \max\{K - |x - A_i|, 0\} である.ただし,|t| は t の絶対値を表す.
すべての鐘を鳴らしたとき,座標 x で聞こえる鐘の音の強さは,座標 x で聞こえるそれぞれの鐘の音の強さの最大値である.
JOI 市にはこの道路に沿って M 個の家があり,古い方から順に 1 から M までの番号が付けられている.家 j (1 ≦ j ≦ M) は座標 B_j にある.
JOI 市の市長であるあなたは,すべての鐘を鳴らしたとき,それぞれの家で聞こえる鐘の音の強さを知りたい.
JOI 市の鐘と家の情報が与えられたとき,すべての鐘を鳴らしたときに座標 B_1, B_2, …, B_M で聞こえる鐘の音の強さを求めるプログラムを作成せよ.
制約
- 1 \leqq N \leqq 250\,000.
- 1 \leqq M \leqq 250\,000.
- 1 \leqq K \leqq 10^9.
- 0 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N).
- A_i \lt A_{i+1} (1 \leqq i \leqq N - 1).
- 0 \leqq B_j \leqq 10^9 (1 \leqq j \leqq M).
- B_j ≠ B_k (1 \leqq j < k \leqq M).
- 入力される値はすべて整数である.
小課題
- (20 点) N = 1,M \leqq 1\,000.
- (20 点) N \leqq 1\,000,M \leqq 1\,000.
- (60 点) 追加の制約はない.
入力
入力は以下の形式で与えられる.
N M K A_1 A_2 \cdots A_N B_1 B_2 \cdots B_M
出力
M 行出力せよ.j 行目 (1 \leqq j \leqq M) には,すべての鐘を鳴らしたときに座標 B_j で聞こえる鐘の音の強さを出力せよ.
入力例 1
1 5 10 20 20 15 28 10 32
出力例 1
10 5 2 0 0
この入力例では,座標 20 に鐘 1 がある.
- 鐘 1 を鳴らしたとき,座標 20 で聞こえる鐘 1 の音の強さは \max\{10 - |20 - 20|, 0\} = 10 である.したがって,1 行目には 10 を出力する.
- 鐘 1 を鳴らしたとき,座標 15 で聞こえる鐘 1 の音の強さは \max\{10 - |15 - 20|, 0\} = 5 である.したがって,2 行目には 5 を出力する.
- 鐘 1 を鳴らしたとき,座標 28 で聞こえる鐘 1 の音の強さは \max\{10 - |28 - 20|, 0\} = 2 である.したがって,3 行目には 2 を出力する.
- 鐘 1 を鳴らしたとき,座標 10 で聞こえる鐘 1 の音の強さは \max\{10 - |10 - 20|, 0\} = 0 である.したがって,4 行目には 0 を出力する.
- 鐘 1 を鳴らしたとき,座標 32 で聞こえる鐘 1 の音の強さは \max\{10 - |32 - 20|, 0\} = 0 である.したがって,5 行目には 0 を出力する.
この入力例はすべての小課題の制約を満たす.
入力例 2
3 4 100 116 194 258 57 155 222 360
出力例 2
41 61 72 0
- 鐘 1,2,3 を鳴らしたとき,座標 57 で聞こえる音の強さはそれぞれ 41,0,0 である.したがって,すべての鐘を鳴らしたときに座標 57 で聞こえる音の強さはこれらの最大値である 41 である.そのため,1 行目には 41 を出力する.
- 鐘 1,2,3 を鳴らしたとき,座標 155 で聞こえる音の強さはそれぞれ 61,61,0 である.したがって,すべての鐘を鳴らしたときに座標 155 で聞こえる音の強さはこれらの最大値である 61 である.そのため,2 行目には 61 を出力する.
- 鐘 1,2,3 を鳴らしたとき,座標 222 で聞こえる音の強さはそれぞれ 0,72,64 である.したがって,すべての鐘を鳴らしたときに座標 222 で聞こえる音の強さはこれらの最大値である 72 である.そのため,3 行目には 72 を出力する.
- 鐘 1,2,3 を鳴らしたとき,座標 360 で聞こえる音の強さはそれぞれ 0,0,0 である.したがって,すべての鐘を鳴らしたときに座標 360 で聞こえる音の強さはこれらの最大値である 0 である.そのため,4 行目には 0 を出力する.
この入力例は小課題 2, 3 の制約を満たす.
入力例 3
10 10 10000 589 2398 6567 28817 29177 31636 45468 66751 82282 97509 2196 54498 80474 61644 18007 38759 85590 72172 79533 69959
出力例 3
9798 970 8192 4893 0 3291 6692 4579 7251 6792
この入力例は小課題 2, 3 の制約を満たす.