Overview

This is a problem where flowers contained in various intervals grow by certain amounts over several days, and we need to find the number of flowers that ultimately reach their target height.

Analysis

In this problem, \(M\) operations of “growing all flowers in interval \([L_j, R_j]\) by \(W_j\)” are performed. A naive approach of adding the growth amount to every flower in the range for each operation would require \(O(N \cdot M)\) computation in the worst case. Under the constraints \(N, M \leq 2 \times 10^5\), this results in a very large amount of computation and would lead to TLE (Time Limit Exceeded).

To efficiently perform uniform addition over intervals, we use a technique called the “Imos method (difference array).” In this method, we add the value at the start of the interval and subtract the value at the position right after the end of the interval, representing the addition over the entire interval in \(O(1)\). Afterward, by computing the prefix sum, we can obtain the total sum applied to each element.

For example, if there are 5 flowers and we want to apply a growth of \(3\) to the interval \([2, 4]\): - For the difference list diff: - diff[1] += 3 - diff[4] -= 3 When we later compute the prefix sum, the value \(3\) is reflected only in the interval \([2, 4]\).

In this way, we record all operations in the difference list, compute the prefix sum just once at the end, calculate the final height for each flower, and determine whether it meets or exceeds the target height.

Algorithm

1. Read the initial height \(H_i\) of each flower.
2. Read the target height \(T_i\) of each flower.
3. While reading the watering information for each day, record the addition of growth amount \(W_j\) to the interval \([L_j, R_j]\) in the difference list diff:
   • diff[L_j - 1] += W_j
   • diff[R_j] -= W_j (converted to 0-indexed)
4. Compute the prefix sum of the difference list to obtain the total growth growth[i] for each flower.
5. For each flower, determine whether the final height \(H_i + \text{growth}[i]\) is greater than or equal to the target \(T_i\), and count such flowers.
6. Output the number of flowers that satisfy the condition.

Complexity

• Time complexity: \(O(N + M)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Since intervals are given in 1-indexed format, they need to be converted to 0-indexed for internal processing.

• Setting the size of the difference list to \(N+1\) prevents out-of-bounds access.

• Note that the final growth values fit within the range of 64-bit integers (in Python, int handles this natively).

  Source Code

import sys
from itertools import accumulate

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    
    H = [int(data[idx+i]) for i in range(N)]
    idx += N
    T = [int(data[idx+i]) for i in range(N)]
    idx += N
    
    # 区間加算クエリを処理するための差分リスト
    diff = [0] * (N + 1)
    
    for _ in range(M):
        L = int(data[idx]) - 1  # 0-indexed
        idx += 1
        R = int(data[idx]) - 1  # 0-indexed
        idx += 1
        W = int(data[idx])
        idx += 1
        
        diff[L] += W
        diff[R + 1] -= W
    
    # 累積和で各区間の合計成長量を計算
    growth = list(accumulate(diff))[:N]
    
    # 各花の最終的な高さを計算し、目標を超えるか判定
    count = 0
    for i in range(N):
        final_height = H[i] + growth[i]
        if final_height >= T[i]:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.