Overview

This problem asks you to find the number of street lights that still have a durability of 1 or more after subtracting the total range-based reductions caused by multiple blizzards from each street light’s initial durability.

Analysis

In a naive approach, for each blizzard, subtracting \(D_j\) from each element in the range \([L_j, R_j]\) of street lights would take \(O(NM)\) time, which is too slow given the constraints \(N, M \leq 2 \times 10^5\).

To efficiently perform range addition (subtraction), we use the imos method (an application of prefix sums). By recording each blizzard’s information in a difference array and computing the prefix sum at the end, we can determine the total reduction for each street light in \(O(N+M)\).

Algorithm

1. Initialize a difference array diff of length \(N+1\) with zeros.
2. For each blizzard \((L_j, R_j, D_j)\):
   • diff[L_j] += D_j
   • diff[R_j+1] -= D_j
3. While computing the prefix sum of the difference array, determine the total reduction total_reduction for each street light \(i\).
4. Count the number of street lights where the initial durability \(H_i\) is greater than the total reduction total_reduction.

Complexity

• Time complexity: \(O(N + M)\)
  • Reading blizzard information: \(O(M)\)
  • Computing the prefix sum and counting: \(O(N)\)
• Space complexity: \(O(N)\)
  • Storing the difference array and durability array: \(O(N)\)

Implementation Notes

• Since array indices are 0-based, adjust the input values \(L_j\) and \(R_j\) by subtracting 1.

• Set the size of the difference array to \(N+1\) to ensure the index R_j+1 does not go out of bounds.

• Properly update the variable total_reduction while computing the prefix sum, and evaluate the condition for each street light.

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
        
    n = int(data[0])
    m = int(data[1])
    H = list(map(int, data[2:2+n]))
    events = []
    index = 2 + n
    for i in range(m):
        l = int(data[index])
        r = int(data[index+1])
        d = int(data[index+2])
        index += 3
        events.append((l-1, r-1, d))
    
    diff = [0] * (n+1)
    for l, r, d in events:
        diff[l] += d
        diff[r+1] -= d
        
    total_reduction = 0
    count = 0
    for i in range(n):
        total_reduction += diff[i]
        if H[i] > total_reduction:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.