Overview

Given \(M\) interval operations that each add \(+1\) to the range \([L_j, R_j]\), we count the number of plants whose final moisture level is at least \(K\).
To efficiently process these range additions, we use a “difference array (imos method).”

Analysis

Key Insight

Each watering operation is “add \(+1\) to all elements in a contiguous interval.”
If we naively apply each such range update directly to the array, a single watering operation may modify up to \(O(N)\) elements, resulting in an overall complexity of \(O(NM)\).

• The constraints are \(N, M \le 2 \times 10^5\)
• A naive approach would require up to \(N \times M = 4 \times 10^{10}\) updates in the worst case, which won’t finish in time (TLE).

How to Solve This (Difference Array)

The operation of adding \(+1\) to the interval \([L, R]\) can be represented using a difference array diff with just two point updates:

• diff[L] += 1
• diff[R+1] -= 1 (if \(R+1\) is within bounds)

After taking the prefix sum of diff, we can recover the number of times each position \(i\) was watered (i.e., the total additions).

Concrete Example

For \(N=5\), adding \(+1\) to the interval \([2,4]\) (1-indexed), which becomes \([1,3]\) in 0-indexed: - diff[1] += 1 - diff[4] -= 1

Taking the prefix sum of diff from left to right, only positions 1 through 3 get +1, while all other positions remain 0.

Algorithm

1. Read the initial moisture array \(A\) from input.
2. Initialize a difference array diff of length \(N+1\) with all zeros.
3. For each watering operation \((L, R)\) (converted to 0-indexed):
   
   • diff[L] += 1
     
   • If \(R+1 < N\), then diff[R+1] -= 1
4. Compute the prefix sum cur of diff, and for each \(i\):
   • The final moisture level is \(A_i + cur\)
   • If this is at least \(K\), increment the answer by 1
5. Output the answer.

Complexity

• Time complexity: \(O(N + M)\)
  (Each watering operation is \(O(1)\); the final prefix sum and comparison take \(O(N)\))
• Space complexity: \(O(N)\)
  (For the difference array diff and array \(A\))

Implementation Notes

• The input values \(L_j, R_j\) are 1-indexed, so in the code we subtract 1 to convert to 0-indexed.

• When accessing diff[R+1], we check that \(R+1\) is within the array bounds (\(< N\)) (in the code: if R + 1 < N:).

• The difference array only becomes meaningful after taking the prefix sum, so don’t forget to compute cur += diff[i] at the end.

• Since \(N, M\) can be large, we use sys.stdin.buffer.read() to read all input at once for faster I/O.

  Source Code

import sys

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

    A = [next(it) for _ in range(N)]
    diff = [0] * (N + 1)

    for _ in range(M):
        L = next(it) - 1
        R = next(it) - 1
        diff[L] += 1
        if R + 1 < N:
            diff[R + 1] -= 1

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

    sys.stdout.write(str(ans))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.