Overview

There are N plants, each with an initial moisture level. After M watering operations that increase the moisture of plants in specified intervals, we need to find the number of plants whose final moisture level is at least K.

Analysis

A naive approach to this problem would be to “directly increment the moisture of every plant in the interval \([L_j, R_j]\) by 1 for each watering operation.” However, this approach has a worst-case time complexity of \(O(M \times N)\), which is too slow given the constraints \(M, N \leq 2 \times 10^5\) (requiring up to \(4 \times 10^{10}\) operations, resulting in TLE).

Instead, we use a “difference array (imos method)” to efficiently perform uniform additions over intervals. With a difference array, each interval addition can be processed in \(O(1)\), and by taking a prefix sum at the end, we can determine the number of additions applied to each element.

For example, to add +1 to the interval \([2, 5]\), we add +1 at index 1 and -1 at index 5 in the difference array, efficiently representing the range update.

Using this technique, we can quickly compute the total increase from all watering operations. Then, by calculating each plant’s final moisture level and checking whether it is at least K, we obtain the answer.

Algorithm

1. Read the initial moisture level \(A_i\) for each plant.
2. Prepare a difference array diff of size \(N+1\) (one extra for boundary handling).
3. For each watering operation \(j\):
   • Add +1 to the interval \([L_j, R_j]\) → diff[L_j - 1] += 1, diff[R_j] -= 1
4. Compute the prefix sum of the difference array to obtain the number of waterings for each plant.
5. For each plant, if “initial moisture + number of waterings” is at least \(K\), increment the count.
6. Output the count.

Complexity

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

Implementation Notes

• Since the difference array uses 0-based indexing, note that the interval \([L, R]\) is updated at diff[L - 1] and diff[R].
• The final prefix sum is computed over diff[:N], and diff[N] is used only as a dummy element.
• sys.stdin.read() is used for fast input reading.

## Source Code

```python
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
    K = int(data[idx]); idx += 1
    
    A = [int(data[i]) for i in range(idx, idx + N)]; idx += N
    
    # 差分配列を用意
    diff = [0] * (N + 1)
    
    for _ in range(M):
        L = int(data[idx]); idx += 1
        R = int(data[idx]); idx += 1
        diff[L-1] += 1
        diff[R] -= 1
    
    # 累積和で水やり回数を計算
    water_added = list(accumulate(diff[:-1]))
    
    # 最終的な水分量を計算し、K以上になる植物をカウント
    count = 0
    for i in range(N):
        final_moisture = A[i] + water_added[i]
        if final_moisture >= K:
            count += 1
    
    print(count)

if __name__ == "__main__":
    main()

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