Overview

Given a row of buildings, multiple explosions occur, each reducing the durability of the center building and its adjacent buildings. The task is to find the number of buildings with durability 1 or more after all explosions.

Analysis

In this problem, each explosion directly affects the durability of buildings, so we need to simulate all explosions in order.

The key observations are as follows: - Each explosion deals \(D_j\) damage to the center building, and \(\lfloor D_j / 2 \rfloor\) damage to its left and right adjacent buildings. - Durability can go negative and must be handled without issues (even collapsed buildings are affected). - Since the number of buildings \(N\) and the number of explosions \(M\) can be up to \(2 \times 10^5\), each explosion must be processed in constant time.

A naive approach (e.g., updating a range of damage each time) may not be fast enough, so it is important to process each explosion in constant time by affecting at most 3 positions (center + left + right).

Algorithm

1. Store the initial durability of each building in an array durability.
2. For each explosion, process as follows:
   • Deal \(D_j\) damage to the center building \(T_j\).
   • If it exists, deal \(\lfloor D_j / 2 \rfloor\) damage to the left adjacent building.
   • If it exists, deal \(\lfloor D_j / 2 \rfloor\) damage to the right adjacent building as well.
3. After all explosions are processed, iterate through the durability array and count the number of buildings with durability 1 or more, then output the result.

This method is efficient since each explosion affects at most 3 elements.

Example

Sample input:

5 2
10 5 8 6 9
3 4
2 6

Initial state: [10, 5, 8, 6, 9]

1st explosion (building 3, power 4): - Building 3: 8 → 4 - Building 2: 5 → 3 - Building 4: 6 → 4

→ [10, 3, 4, 4, 9]

2nd explosion (building 2, power 6): - Building 2: 3 → -3 - Building 1: 10 → 7 - Building 3: 4 → 1

→ [7, -3, 1, 4, 9]

Buildings with durability 1 or more: buildings 1, 3, 4, 5 → total of 4

Complexity

• Time complexity: \(O(N + M)\)
  (\(O(N)\) for initialization, \(O(1) \times M\) for processing each explosion)
• Space complexity: \(O(N)\)
  (array to store durability values)

Implementation Notes

• Building numbers are given as 1-indexed in the input, so they need to be converted to 0-indexed for internal processing.
• When checking for left and right neighbors, be careful not to access out-of-bounds indices for edge buildings (index 0 or N-1).
• Damage should be computed using integer division (//) to correctly perform floor division.

## Source Code

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    
    H = list(map(int, data[2:2+N]))
    
    # 爆発情報をパース
    explosions = []
    for j in range(M):
        T = int(data[2 + N + 2*j]) - 1  # 0-indexedにする
        D = int(data[2 + N + 2*j + 1])
        explosions.append((T, D))
    
    # 各建物の耐久値を管理（初期値）
    durability = H[:]
    
    # 各爆発を処理
    for T, D in explosions:
        # 中心の建物
        durability[T] -= D
        
        # 左隣の建物（存在すれば）
        if T > 0:
            durability[T - 1] -= D // 2
            
        # 右隣の建物（存在すれば）
        if T < N - 1:
            durability[T + 1] -= D // 2
    
    # 耐久値が1以上（倒壊していない）建物の数をカウント
    count = sum(1 for d in durability if d >= 1)
    print(count)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.