ラウンドは高々 \(N\) で終わります。単純に毎ターン免疫力を計算すると \(\Theta(N^2)\) かかりますから、これを高速化したいです。

毎ターン各 \(i\) について減算する値は \(0, D, 2D\) しかないです。そして、この値が変わらない間は、簡単な式で免疫力および免疫力が \(0\) を下回るラウンドを計算することができます。

そのため、これが切り替わった瞬間だけ再計算することにすれば、各 \(i\) について高々 \(3\) 回免疫力を計算すれば良いことになり高速になりそうです。

あとは、適切にこれらの更新を管理すればよいです。具体的には、 以下を管理しておけば十分です。

各 \(i\) について

• 最後に免疫力を更新した時の免疫力
• 最後に免疫力を更新した時のラウンド
• 今減算されている値
• 減算されている値が変わらないとした時、免疫力が \(0\) 以下になるラウンド

を管理します。最後の要素については、ラウンド \(\to\) \(i\) もできるようにしておけば良いです。

これらの更新は、 \(O(\log N)\) や \(O(1)\) で可能です。

実装例

n, d = map(int, input().split())
h = list(map(int, input().split()))

r = [[] for i in range(n + 1)]
for i in range(n):
    if h[i] <= 0: r[0].append(i)

ok = [0] * n # 感染したかどうか
px = [0] * n # 最後に免疫力を更新したラウンド
nd = [0] * n # いま減算される値
for x in range(n + 1):
    upd = []
    for i in r[x]:
        if ok[i]: continue
        ok[i] = 1
        if 0 <= i-1: upd.append(i-1)
        if i+1 < n: upd.append(i+1)
    if not upd: break
    for i in upd:
        if ok[i]: continue
        h[i] -= nd[i] * (x - px[i])
        nd[i] += d
        px[i] = x
        y = x + (h[i] - 1) // nd[i] + 1
        if y <= n: r[y].append(i)

print(sum(ok))