Overview

Given \(N\) buildings that experience \(M\) explosions, where each explosion deals damage to the center building and its left and right adjacent buildings. The problem asks to find the number of buildings with durability of at least \(1\) remaining after all explosions.

Analysis

Key Insight

The most important observation in this problem is that we only need to know the total damage each building ultimately receives.

Regardless of the order of explosions, the cumulative damage to each building remains the same. For example: - Building \(i\) receives damage of power \(D\) when it is the center of an explosion - Building \(i\) receives damage of power \(\lfloor D/2 \rfloor\) when an adjacent building \(i-1\) or \(i+1\) is the center

Issues with the Naive Approach

Since each explosion updates at most 3 buildings, \(M\) explosions require \(O(M)\) computation. In fact, the naive approach is fast enough for this problem.

However, if the setting were such that “shockwaves spread infinitely (decreasing with distance)”, we would need to update \(O(N)\) buildings per explosion, resulting in \(O(NM)\) total time which could cause TLE.

Key Points of the Solution

Manage the damage each building receives using an array, and after processing all explosions, calculate the remaining durability of each building.

Algorithm

1. Initialize damage array: Initialize an array damage of length \(N\) with \(0\)
2. Process each explosion: For each of the \(M\) explosions
   • Add power \(D_j\) to the center building \(T_j\)
   • If left neighbor \(T_j - 1\) exists, add \(\lfloor D_j / 2 \rfloor\)
   • If right neighbor \(T_j + 1\) exists, add \(\lfloor D_j / 2 \rfloor\)
3. Count surviving buildings: For each building \(i\), it survives if \(H_i - \text{damage}[i] \geq 1\)

Concrete Example

With \(N = 3\), \(H = [10, 5, 8]\), and an explosion centered at building 2 with power 6: - Building 1 (left neighbor): Damage \(\lfloor 6/2 \rfloor = 3\) - Building 2 (center): Damage \(6\) - Building 3 (right neighbor): Damage \(\lfloor 6/2 \rfloor = 3\)

Final durability: \([10-3, 5-6, 8-3] = [7, -1, 5]\)

Building 2 collapses (durability \(\leq 0\)), 2 buildings survive.

Complexity

• Time complexity: \(O(N + M)\)
  • Reading input: \(O(N + M)\)
  • Processing each explosion: \(O(1)\) (updating only a constant number of buildings) × \(M\) times = \(O(M)\)
  • Counting survivors: \(O(N)\)
• Space complexity: \(O(N)\)
  • Storing the damage array and durability array: \(O(N)\)

Implementation Notes

• Conversion to 0-indexed: The problem uses building numbers starting from \(1\), but arrays start from \(0\), so adjust with T -= 1 after reading input
• Boundary checks: When a building at the left edge (\(T = 0\)) or right edge (\(T = N-1\)) is the center, conditional branching is needed to avoid accessing non-existent adjacent buildings
• Integer floor division: In Python, use the // operator to compute \(\lfloor D/2 \rfloor\)

Source Code

def main():
    import sys
    input = sys.stdin.readline
    
    N, M = map(int, input().split())
    H = list(map(int, input().split()))
    
    # Accumulate damage to each building
    damage = [0] * N
    
    for _ in range(M):
        T, D = map(int, input().split())
        T -= 1  # 0-indexed
        
        # Center building
        damage[T] += D
        
        # Left neighbor building (if exists)
        if T > 0:
            damage[T - 1] += D // 2
        
        # Right neighbor building (if exists)
        if T < N - 1:
            damage[T + 1] += D // 2
    
    # Count buildings that have not collapsed
    count = 0
    for i in range(N):
        if H[i] - damage[i] >= 1:
            count += 1
    
    print(count)

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.