Overview

This is a problem where you water each flower multiple times and need to find the number of flowers whose final height meets or exceeds a target value.

Analysis

The final height of each flower \(i\) is its initial height \(H_i\) plus the sum of \(W_j\) values for all watering operations that affect that flower. A naive approach that checks all watering operations for each flower would take \(O(N \times M)\) time, which is too slow given the constraints (\(N, M \leq 200,000\)) to meet the time limit. Therefore, we need an efficient method to handle range addition operations.

Algorithm

This problem can be reduced to “range addition” and “querying final values.” To handle this efficiently, we use the imos method (an application of prefix sums).

1. Prepare an array diff of length \(n+1\) (0-indexed).
2. For each watering operation \((L_j, R_j, W_j)\):
   • diff[L_j] += W_j
   • diff[R_j+1] -= W_j
3. Compute the prefix sum of the array diff. The value at each position \(i\) then represents the total amount of water (\(total\_water\)) that flower \(i\) received.
4. For each flower \(i\), check whether the final height \(H_i + total\_water\) is at least the target \(T_i\), and count the number of flowers that satisfy this condition.

Complexity

• Time complexity: \(O(N + M)\)
  • Processing watering operations: \(O(M)\)
  • Computing prefix sums and checking flowers: \(O(N)\)
• Space complexity: \(O(N)\)
  • The array diff has size \(n+1\)

Implementation Notes

• Since flower numbers in the input are 1-indexed, you need to convert to 0-indexed (\(-1\)) when accessing arrays.

• Allocate the array diff with size \(n+1\) and be careful that the index R+1 does not go out of bounds.

• By performing the flower condition checks simultaneously while computing the prefix sum, we avoid extra loops.

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    n = int(next(it)); m = int(next(it))
    H = [int(next(it)) for _ in range(n)]
    T = [int(next(it)) for _ in range(n)]
    queries = []
    for _ in range(m):
        L = int(next(it)); R = int(next(it)); W = int(next(it))
        queries.append((L-1, R-1, W))
    
    diff = [0] * (n+1)
    for L, R, W in queries:
        diff[L] += W
        diff[R+1] -= W
    
    total_water = 0
    count = 0
    for i in range(n):
        total_water += diff[i]
        final_height = H[i] + total_water
        if final_height >= T[i]:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.