Overview

Given \(N\) streetlights, after \(M\) blizzards (bulk subtraction over intervals), we need to find the number of streetlights that still have a durability of \(1\) or more. By using the imos method (difference array), we can efficiently handle additions over intervals.

Analysis

Naive Approach and Its Problems

The simplest method is to reduce the durability of each streetlight from \(L_j\) to \(R_j\) by \(D_j\) one by one for each blizzard. However, this method requires updating up to \(N\) streetlights per blizzard, resulting in a worst-case time complexity of \(O(N \times M)\) overall. Since both \(N\) and \(M\) can be up to \(2 \times 10^5\), this amounts to \(4 \times 10^{10}\) operations, which will not fit within the time limit (TLE).

Key Insight

For each streetlight \(i\), what we ultimately want to know is the total damage from all blizzards \(\text{damage}[i]\). That is:

\[\text{damage}[i] = \sum_{\substack{j : L_j \leq i \leq R_j}} D_j\]

Once we know this, we simply check whether \(H_i - \text{damage}[i] \geq 1\).

The operation of “adding a uniform value to an interval and wanting to know the total for each element at the end” can be processed in \(O(1)\) per operation using the imos method (difference array).

Algorithm

How the Imos Method Works

Prepare a difference array \(\text{diff}\) of length \(N+1\) (all initial values are \(0\)).

For each blizzard \((L_j, R_j, D_j)\): - Add \(D_j\) to \(\text{diff}[L_j - 1]\) - Subtract \(D_j\) from \(\text{diff}[R_j]\)

Concrete example: For \(N = 5\) and blizzard \((L=2, R=4, D=3)\)

index	0	1	2	3	4
diff	0	+3	0	0	-3

Taking the prefix sum of this difference array:

index	0	1	2	3	4
damage	0	3	3	3	0

Damage of \(3\) is correctly applied to streetlights 2–4 (0-indexed 1–3).

Overall Procedure

1. Prepare the difference array \(\text{diff}\)
2. For each of the \(M\) blizzards, record it in the difference array in \(O(1)\)
3. While computing the prefix sum of the difference array, calculate the cumulative damage \(\text{cumulative}\) for each streetlight \(i\)
4. If \(H_i - \text{cumulative} \geq 1\), the streetlight has not collapsed, so count it
5. Output the final count

Complexity

• Time complexity: \(O(N + M)\)
  • Recording in the difference array is \(O(M)\), and computing the prefix sum and checking is \(O(N)\)
• Space complexity: \(O(N)\)
  • \(O(N)\) each for the difference array and the durability array

Implementation Notes

• 1-indexed to 0-indexed conversion: In the problem statement, streetlights are numbered starting from \(1\), but arrays are \(0\)-indexed, so we add at position \(L_j - 1\) and subtract at position \(R_j\).

• Beware of overflow: Since \(D_j\) can be up to \(10^9\) and \(M\) can be up to \(2 \times 10^5\), the total damage can reach approximately \(2 \times 10^{14}\). In Python, there is no integer overflow issue, but in C++ and similar languages, you need to use long long.

• Fast input: Since \(N\) and \(M\) can be large, in Python we speed up input by reading everything at once with sys.stdin.buffer.read().

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    H = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    
    # imos法で各街灯へのダメージ合計を計算
    diff = [0] * (N + 1)
    for j in range(M):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        D = int(input_data[idx]); idx += 1
        diff[L - 1] += D
        diff[R] -= D
    
    count = 0
    cumulative = 0
    for i in range(N):
        cumulative += diff[i]
        if H[i] - cumulative >= 1:
            count += 1
    
    print(count)

main()

---

This editorial was generated by claude4.6opus-thinking.