Overview

Given \(N\) flowers, we perform \(M\) range uniform additions and count the number of flowers whose final height meets or exceeds the target. We use the imos method (difference array) to efficiently process the range additions.

Analysis

Naive Approach and Its Issues

The simplest method is, for each watering operation \(j\), to add \(W_j\) to the height of each flower from \(L_j\) to \(R_j\) one by one. However, this method requires updating up to \(N\) flowers per watering operation, resulting in an overall time complexity of \(O(N \times M)\). Since both \(N\) and \(M\) can be up to \(2 \times 10^5\), this leads to up to \(4 \times 10^{10}\) operations in the worst case, causing TLE (Time Limit Exceeded).

Key Insight

Each watering operation takes the form “add \(W_j\) uniformly to the interval \([L_j, R_j]\).” When we need to perform a large number of such uniform range additions and then compute the value at each position all at once at the end, the imos method (difference array) is extremely effective.

Algorithm

How the Imos Method (Difference Array) Works

Prepare a difference array diff of size \(N+1\), initialized entirely to \(0\).

When we want to add \(W\) to the interval \([L, R]\), we perform only the following two operations:

• diff[L] += W (start adding at the beginning of the interval)
• diff[R+1] -= W (stop adding right after the end of the interval)

Concrete example: For \(N = 5\), adding \(W = 3\) to the interval \([2, 4]\)

diff: [0, 0, 0, 0, 0, 0]  (indices 0 to 5)
After operation: [0, +3, 0, 0, -3, 0]  (diff[1] += 3, diff[4] -= 3)  *0-indexed

Taking the prefix sum of the difference array:

Prefix sum: [0, 3, 3, 3, 0, 0]

We can see that exactly \(3\) has been added to indices 1 through 3 (flower 2 through flower 4).

Overall Flow

1. Prepare the difference array diff
2. Record each of the \(M\) watering operations in the difference array in \(O(1)\)
3. Compute the prefix sum of the difference array, calculating the final height of flower \(i\) as \(H_i + \text{prefix\_sum}_i\)
4. Count the number of flowers where \(H_i + \text{prefix\_sum}_i \geq T_i\)

Complexity

• Time complexity: \(O(N + M)\)
  • Recording in the difference array: \(O(1)\) per operation for \(M\) operations gives \(O(M)\)
  • Prefix sum computation and comparison: \(O(N)\)
• Space complexity: \(O(N)\)
  • \(O(N)\) each for the difference array, initial heights, and target heights

Implementation Notes

• 1-indexed to 0-indexed conversion: Since the problem numbers flowers starting from \(1\), when managing the difference array in 0-indexed fashion, we use diff[L-1] += W and diff[R] -= W (this is the approach adopted in the code).

• Overflow caution: \(W_j\) can be up to \(10^9\) and there can be up to \(2 \times 10^5\) operations, so the prefix sum can reach approximately \(2 \times 10^{14}\). Additionally, \(T_i\) can be up to \(10^{18}\). Python has no integer overflow issues so there is no concern, but in C++ and similar languages, long long must be used.

• Fast input: Since \(N\) and \(M\) can be large, reading all input at once with sys.stdin.buffer.read() speeds up the input process.

  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
    T = [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
        W = int(input_data[idx]); idx += 1
        diff[L - 1] += W
        if R < N:
            diff[R] -= W
    
    count = 0
    cumsum = 0
    for i in range(N):
        cumsum += diff[i]
        if H[i] + cumsum >= T[i]:
            count += 1
    
    print(count)

main()

---

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