概要

各爆発が与えるダメージを建物ごとに合計し、最終的な耐久値 \(H_i-\text{(合計ダメージ)}\) が \(1\) 以上の建物の数を数えます。

考察

この問題の重要な点は、各爆発の影響範囲が「中心」と「左右の隣接」の最大3つの建物に限られることです。つまり、爆発 \(j\) は - 建物 \(T_j\) に \(D_j\) - 建物 \(T_j-1, T_j+1\)（存在すれば）に \(\lfloor D_j/2 \rfloor\)

だけ耐久値を減らします。

また、「倒壊した建物も残り続けてさらにダメージを受ける」とありますが、最終的に知りたいのは 全爆発後の耐久値が \(1\) 以上かどうかです。途中で倒壊したかどうかに関係なく、結局は「各建物が受けたダメージ総量」を引けば最終耐久値が求まります（途中経過をシミュレーションする必要がありません）。

素朴に「爆発のたびに配列を更新して倒壊判定も逐次やる」こと自体は、この問題では影響範囲が小さいので実は \(O(M)\) で済みます。そこでさらに単純化し、建物ごとに受けたダメージの合計だけを記録して最後にまとめて判定する、という方針にできます。

具体例： - ある建物 \(i\) が複数回隣接ダメージを受けても、最終的にはそれらを足した合計を \(H_i\) から引くだけでよいです。

アルゴリズム

1. 長さ \(N\) の配列 dmg を用意し、全て \(0\) で初期化する（dmg[i] は建物 \(i\) が受けるダメージ総量）。
2. 各爆発 \((T, D)\) について（入力は1-indexedなので注意して0-indexedに直す）：
   • dmg[T] += D
   • a = D // 2 として
     • 左が存在するなら dmg[T-1] += a
     • 右が存在するなら dmg[T+1] += a
3. 最後に全ての建物について、\(H_i - \text{dmg}[i] \ge 1\) を満たす個数を数えて出力する。

計算量

• 時間計算量: \(O(N + M)\)（各爆発で最大3回の加算、最後に全建物を1回チェック）
• 空間計算量: \(O(N)\)（ダメージ合計配列 dmg）

実装のポイント

• 入力の建物番号 \(T_j\) は 1-indexed なので、コード内では t = T_j - 1 に変換します。

• 両端の建物では隣が存在しないため、t>0 や t+1<N の境界チェックが必要です。

• \(\lfloor D/2 \rfloor\) は Python では D // 2 で求められます。

• 制約が大きいので、sys.stdin.buffer.read() で高速入力にしています。

  ソースコード

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    N = int(next(it))
    M = int(next(it))
    H = [int(next(it)) for _ in range(N)]
    dmg = [0] * N

    for _ in range(M):
        t = int(next(it)) - 1
        d = int(next(it))
        dmg[t] += d
        a = d // 2
        if t > 0:
            dmg[t - 1] += a
        if t + 1 < N:
            dmg[t + 1] += a

    ans = 0
    for i in range(N):
        if H[i] - dmg[i] >= 1:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。