Overview

Sum up the damage dealt by each explosion for each building, and count the number of buildings whose final durability \(H_i-\text{(total damage)}\) is \(1\) or more.

Analysis

The key point of this problem is that each explosion’s area of effect is limited to at most 3 buildings: the “center” and its “left and right neighbors”. Specifically, explosion \(j\) reduces durability by: - \(D_j\) to building \(T_j\) - \(\lfloor D_j/2 \rfloor\) to buildings \(T_j-1, T_j+1\) (if they exist)

Additionally, the problem states that “collapsed buildings remain and continue to take damage,” but what we ultimately want to know is whether the durability after all explosions is \(1\) or more. Regardless of whether a building collapsed midway, the final durability can be determined simply by subtracting the “total damage each building received” (there is no need to simulate the intermediate states).

A naive approach of “updating the array and checking for collapse with each explosion” would actually run in \(O(M)\) for this problem since the area of effect is small. We can simplify even further by adopting the strategy of only recording the total damage received by each building and then checking everything at the end.

Concrete example: - Even if a building \(i\) receives adjacent damage multiple times, we ultimately just need to subtract the sum of all that damage from \(H_i\).

Algorithm

1. Prepare an array dmg of length \(N\), initialized to all \(0\) (dmg[i] represents the total damage building \(i\) receives).
2. For each explosion \((T, D)\) (note that the input is 1-indexed, so convert to 0-indexed):
   • dmg[T] += D
   • Let a = D // 2, then:
     • If the left neighbor exists: dmg[T-1] += a
     • If the right neighbor exists: dmg[T+1] += a
3. Finally, count and output the number of buildings satisfying \(H_i - \text{dmg}[i] \ge 1\).

Complexity

• Time complexity: \(O(N + M)\) (at most 3 additions per explosion, plus one check over all buildings at the end)
• Space complexity: \(O(N)\) (damage total array dmg)

Implementation Notes

• Building numbers \(T_j\) in the input are 1-indexed, so convert them in the code with t = T_j - 1.

• For buildings at the endpoints, neighbors may not exist, so boundary checks like t>0 and t+1<N are necessary.

• \(\lfloor D/2 \rfloor\) can be computed in Python as D // 2.

• Since the constraints are large, sys.stdin.buffer.read() is used for fast input.

  Source Code

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()

This editorial was generated by gpt-5.2-high.