/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 466 点
問題文
高橋君は、ある村の保健担当者です。村には N 人の住民が一列に並んで暮らしており、左から順に 1 から N までの番号が付けられています。
各住民 i には免疫力を表す整数 H_i が定められています。免疫力が 0 以下の住民は感染状態です。一度感染状態になった住民は、その後も感染状態のままです。
感染はラウンド制で広がります。はじめ、H_i \leq 0 である住民は感染状態であり、これをラウンド 0 の感染状態とします。
ラウンド 1,2,\ldots では、次の処理を順に行います。
- そのラウンドの開始時点で感染状態にあるすべての住民が、自分に隣接する住民（番号が 1 だけ異なる住民）の免疫力をそれぞれ D だけ減少させます。
- ある住民の左右両方の隣人が感染状態である場合、その住民の免疫力は合計で 2D 減少します。
- 免疫力が 0 以下になった住民は、このラウンドの終了時に新たに感染状態になります。
- このラウンドで新たに感染状態になった住民が 1 人もいなかった場合、伝播はただちに終了し、それ以降のラウンドは行われません。
高橋君は、伝播が終了した時点で感染状態になっている住民の人数を求めたいです。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq D \leq 10^9
- -10^9 \leq H_i \leq 10^9 (1 \leq i \leq N)
- 入力はすべて整数である
入力
N D H_1 H_2 \ldots H_N
出力
伝播が終了した時点で感染状態になっている住民の人数を 1 行で出力せよ。
入力例 1
7 3 2 0 5 4 8 0 2
出力例 1
7
入力例 2
5 2 10 -1 10 10 10
出力例 2
1
入力例 3
15 6 18 11 -4 20 5 35 7 14 28 0 16 9 40 3 22
出力例 3
2
入力例 4
50 10 15 28 -3 45 12 80 5 70 35 -1 60 22 11 95 40 8 75 18 6 55 30 -20 90 4 14 100 65 25 9 85 13 7 120 50 -5 33 44 2 68 16 27 0 58 73 19 81 3 39 10 92
出力例 4
5
入力例 5
1 1000000000 1000000000
出力例 5
0
Score : 466 pts
Problem Statement
Takahashi is a health official in a certain village. In this village, N residents live in a single row, numbered 1 to N from left to right.
Each resident i has an integer H_i representing their immunity. A resident whose immunity is 0 or less is in an infected state. Once a resident becomes infected, they remain infected.
The infection spreads in rounds. Initially, residents with H_i \leq 0 are infected, which we consider as the infected state at Round 0.
In Round 1, 2, \ldots, the following processes are performed in order:
- Every resident who is infected at the start of that round decreases the immunity of their adjacent residents (residents whose indices differ by exactly 1) by D each.
- If both the left and right neighbors of a resident are infected, that resident's immunity decreases by 2D in total.
- Residents whose immunity becomes 0 or less will newly become infected at the end of this round.
- If no residents newly become infected during this round, the spread terminates immediately, and no subsequent rounds are conducted.
Takahashi wants to find the number of residents who are infected when the spread ends.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq D \leq 10^9
- -10^9 \leq H_i \leq 10^9 (1 \leq i \leq N)
- All input values are integers.
Input
N D H_1 H_2 \ldots H_N
Output
Print the number of residents who are infected when the spread ends in a single line.
Sample Input 1
7 3 2 0 5 4 8 0 2
Sample Output 1
7
Sample Input 2
5 2 10 -1 10 10 10
Sample Output 2
1
Sample Input 3
15 6 18 11 -4 20 5 35 7 14 28 0 16 9 40 3 22
Sample Output 3
2
Sample Input 4
50 10 15 28 -3 45 12 80 5 70 35 -1 60 22 11 95 40 8 75 18 6 55 30 -20 90 4 14 100 65 25 9 85 13 7 120 50 -5 33 44 2 68 16 27 0 58 73 19 81 3 39 10 92
Sample Output 4
5
Sample Input 5
1 1000000000 1000000000
Sample Output 5
0