Overview

Given \(N\) buildings, \(M\) explosions occur, each dealing damage to a specified location and its two neighbors. The problem asks to find the number of buildings that survive after all explosions—that is, buildings whose total damage received does not exceed their initial durability.

Analysis

1. Focusing on the area of effect of explosions

At first glance, this might seem to require complex simulation, but the range affected by each explosion is very limited. When an explosion occurs at building \(T_j\), only the following up to 3 buildings take damage:

• Building \(T_j\) (center): damage \(D_j\)
• Building \(T_j - 1\) (left neighbor): damage \(\lfloor D_j / 2 \rfloor\)
• Building \(T_j + 1\) (right neighbor): damage \(\lfloor D_j / 2 \rfloor\)

2. Accumulating damage

Even if a building is destroyed by an explosion, its wreckage remains and does not block subsequent shockwaves. In other words, the final total damage each building receives is simply the sum of “damage from explosions occurring at that building” and “shockwave damage from explosions occurring at its neighbors”.

There is no need to worry about the order of explosions; we just need to calculate the total damage to each building after all explosions have finished.

3. Estimating computational complexity

If we updated all \(N\) buildings for each explosion, the total complexity would be \(O(N \times M)\), which would not fit within the time limit given the constraints (\(N, M \le 2 \times 10^5\)). However, in this problem, each explosion only updates at most 3 locations, so processing all explosions completes in \(O(M)\). Combined with the \(O(N)\) for the final survival check of each building, this is well within the time limit.

Algorithm

1. Prepare an array damage of length \(N\), initialized to all \(0\)s.
2. Process the \(M\) explosion events in order. For each explosion \((T_j, D_j)\):
   • Add \(D_j\) to damage[T_j].
   • Add \(\lfloor D_j / 2 \rfloor\) to damage[T_j - 1] (if the left neighbor exists).
   • Add \(\lfloor D_j / 2 \rfloor\) to damage[T_j + 1] (if the right neighbor exists).
3. After all processing is complete, for each building \(i = 1, \ldots, N\), compare the initial durability \(H_i\) with damage[i].
4. Count and output the number of buildings satisfying \(H_i > damage[i]\) (i.e., those with at least \(1\) durability remaining).

Complexity

• Time complexity: \(O(N + M)\)
  • Reading input takes \(O(N + M)\), processing explosions takes \(O(M)\), and the final aggregation takes \(O(N)\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for the array storing durability values and the array storing accumulated damage.

Implementation Notes

• Conversion to 0-indexed: The problem statement numbers buildings from \(1\) to \(N\), but it is easier to manage them as \(0\) to \(N-1\) in program arrays. In that case, you need conditional checks to ensure that adjacent building indices do not go out of bounds (\(-1\) or \(N\)).

• Fast I/O: Since \(N\) and \(M\) can be large, repeatedly calling Python’s input() may be slow. It is more efficient to read all input at once using something like sys.stdin.read().split().

• Integer floor division: In Python, you can easily compute “\(\lfloor D_j / 2 \rfloor\) (floor function)” as described in the problem statement by using the // operator.

  Source Code

import sys

def solve():
    # 入力を一括で読み込み、空白で分割してリスト化する
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    # 建物の数 N と爆発の回数 M を取得
    N = int(input_data[0])
    M = int(input_data[1])
    
    # 各建物の初期耐久値 H_i を取得
    # H は 0-indexed で管理する (建物 1 は H[0])
    H = list(map(int, input_data[2:2+N]))
    
    # 各建物が受ける累積ダメージを格納する配列
    damage = [0] * N
    
    # 爆発情報を順番に処理
    # 爆発の情報は input_data の N+2 番目の要素から始まる
    ptr = 2 + N
    for _ in range(M):
        t_j = int(input_data[ptr])
        d_j = int(input_data[ptr+1])
        ptr += 2
        
        # 建物番号を 0-indexed のインデックスに変換
        idx = t_j - 1
        
        # 爆発の中心となる建物へのダメージ
        damage[idx] += d_j
        
        # 衝撃波による隣接する建物へのダメージ (floor(D_j / 2))
        shock_damage = d_j // 2
        if shock_damage > 0:
            # 左隣の建物が存在する場合
            if idx > 0:
                damage[idx - 1] += shock_damage
            # 右隣の建物が存在する場合
            if idx < N - 1:
                damage[idx + 1] += shock_damage
        
    # すべての爆発が終わった後、生き残っている建物をカウント
    # 耐久値 H[i] から累積ダメージ damage[i] を引いた値が 1 以上であれば倒壊していない
    surviving_count = 0
    for i in range(N):
        if H[i] > damage[i]:
            surviving_count += 1
            
    # 結果を出力
    sys.stdout.write(str(surviving_count) + '\n')

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.