레이팅 미적용JOI 平原は東西方向に広がるとても大きな平原である.この平原は数直線と見なすことができ,各地点は
東向きを正とする座標であらわされる.JOI 平原は冬を迎えN 個の雪玉が異なる座標に作られた.雪玉に
は西から順に1 からN までの番号が付いている.最初,雪玉i (1 ≦i ≦N) の座標は整数Xi であった.
またJOI 平原は冬に強い風が吹くことで知られている.あなたはQ 日間の風の観測データを入手した.j
日目(1 ≦j ≦Q) の風のデータは整数W j であらわされる.W j が負のときは西向きに,W j が負でないとき
は東向きに,強さ|W j| の風が吹いたことを意味する.
風が吹くと,雪玉は風と同じ向きに,風の強さと同じ距離だけ転がる.すなわちj 日目(1 ≦j ≦Q) の始
めに座標x に雪玉があったとき,その雪玉は座標x から座標x + W j まで転がる.j 日目の終わりには,そ
の雪玉の座標はx + W j になる.ただし,各日においてすべての雪玉が同時に,同じ速さで転がる.
最初,JOI 平原全体に雪が積もっていた.雪が積もっている範囲を雪玉が転がると,雪が付着し,雪玉の
重さが増え,その範囲の雪はなくなる.すなわち,a を整数とし,座標a から座標a + 1 までの範囲に雪が
残っているとする.このとき,雪玉がこの範囲を転がると,その雪玉の重さが1 増えて,座標a から座標
a + 1 までの範囲の雪がなくなる.ただし,雪が残っていない範囲を雪玉が転がったとしても,雪玉の重さ
は変わらない.
最初,すべての雪玉の重さは0 であった.また,観測したQ 日間に新たに雪は降らなかった.
あなたはQ 日目の終わりにおける雪玉の重さを知りたい.
雪玉の最初の座標,Q 日間の風の観測データが与えられたとき,Q 日目の終わりにおける,それぞれの雪
玉の重さを求めるプログラムを作成せよ.
• 1 ≦N ≦200 000.
• 1 ≦Q ≦200 000.
• |Xi| ≦1 000 000 000 000 (= 1012) (1 ≦i ≦N).
• Xi < Xi+1 (1 ≦i ≦N −1).
• |W j| ≦1 000 000 000 000 (= 1012) (1 ≦j ≦Q).
- (33 点) N ≦2 000,Q ≦2 000.
- (67 点) 追加の制約はない.
入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
N Q
X1 · · · XN
W1
...
WQ
第20 回日本情報オリンピック(JOI 2020/2021) 本選
2021 年2 月14 日(オンライン開催)
標準出力にN 行で出力せよ.i 行目(1 ≦i ≦N) にはQ 日目の終わりにおける,雪玉i の重さを出力せよ.
4 3
-2 3 5 8
2
-4
7
5
4
2
6
1 4
1000000000000
1000000000000
-1000000000000
-1000000000000
-1000000000000
3000000000000
10 10
-56 -43 -39 -31 -22 -5 0 12 18 22
-3
0
5
-4
-2
10
-13
-1
9
6
14
8
7
9
11
10
9
8
5
10