Overview

We process the growth amounts added in bulk to intervals \([L_j, R_j]\) across all days at once, then count the number of flowers that meet their target \(T_i\).

Analysis

Each day \(j\)’s watering is an “range addition,” so a naive approach would: - Add \(W_j\) to every flower in the interval for each day

This results in a worst case of \(O(NM)\) (up to \(2\times 10^5 \cdot 2\times 10^5\)), which is far too slow.

The key insight is that all we ultimately need to know is “how much each flower has grown in total”, and there is no need to apply the updates day by day.

Therefore, we use a difference array (imos method) to efficiently aggregate range additions.

For example, to add \(+3\) to the interval \([2,4]\) with \(N=5\) (1-indexed): - In the difference array diff, set diff[2] += 3, diff[5] -= 3 (one position past the right end of the interval)

Then, taking the prefix sum of diff gives the added amount at each position. Multiple intervals can similarly be recorded by “only their endpoints,” and a single prefix sum at the end yields the total growth for each flower.

Algorithm

1. Prepare a difference array diff of length \(N\) (in practice, allocate length \(N+1\) for convenience).
2. For each day \(j\)’s operation \((L_j, R_j, W_j)\) (converted to 0-indexed):
   • diff[L_j] += W_j
   • diff[R_j+1] -= W_j (only when \(R_j+1 < N\); if using a sentinel, you can always write it)
3. Compute the prefix sum cur of diff from left to right — this gives the “total growth” of flower \(i\).
4. For each flower \(i\), compute the final height \(H_i + cur\) and count it if \(H_i + cur \ge T_i\).
5. Output the count.

Complexity

• Time complexity: \(O(N + M)\) (applying interval information \(M\) times + prefix sum and comparison \(N\) times)
• Space complexity: \(O(N)\) (difference array)

Implementation Notes

• Since the input has \(N, M \le 2\times 10^5\), using fast input methods like sys.stdin.buffer.read() in Python is recommended.

• \(L_j, R_j\) are 1-indexed in the input, so subtracting \(1\) to convert to 0-indexed makes implementation easier.

• The total growth and target values \(T_i\) can be on the order of \(10^{18}\), but Python’s int has arbitrary precision so it can be computed directly (other languages would need int64).

• Be careful not to forget the condition R+1 < N when handling the right end of the difference array, as it would cause an out-of-bounds access (the provided code correctly handles this branching).

  Source Code

import sys

def main():
    it = map(int, sys.stdin.buffer.read().split())
    N = next(it)
    M = next(it)

    H = [next(it) for _ in range(N)]
    T = [next(it) for _ in range(N)]

    diff = [0] * (N + 1)  # diff[N] is sentinel
    for _ in range(M):
        L = next(it) - 1
        R = next(it) - 1
        W = next(it)
        diff[L] += W
        if R + 1 < N:
            diff[R + 1] -= W

    cur = 0
    ans = 0
    for i in range(N):
        cur += diff[i]
        if H[i] + cur >= T[i]:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.