Overview

This is a problem where you perform \(M\) interval watering operations on \(N\) plants and count the number of plants whose final moisture level is at least \(K\). We use the “imos method” (difference array technique) to efficiently process the range additions.

Analysis

Naive Approach and Its Issues

The simplest method is to increment the moisture level by 1 for every plant in the target range for each watering operation.

for j in range(M):
    for i in range(L[j], R[j]+1):
        A[i] += 1

However, with this method, in the worst case, a single watering operation can target all \(N\) plants. Since there are \(M\) watering operations, the overall time complexity is \(O(NM)\).

When both \(N\) and \(M\) are at most \(2 \times 10^5\), \(O(NM)\) amounts to approximately \(4 \times 10^{10}\) operations, which will not finish within the time limit (TLE).

Solution: The Imos Method

By using the “imos method,” we can record each range addition in \(O(1)\) and then compute the value at each position in \(O(N)\) by taking a prefix sum at the end.

Algorithm

How the Imos Method Works

In the imos method, an addition over the interval \([L, R]\) is recorded as follows:

1. Prepare a difference array diff
2. To add \(+1\) to the interval \([L, R]\):
   • diff[L] += 1 (increase starts here)
   • diff[R+1] -= 1 (increase ends here)
3. Finally, take the prefix sum of diff to obtain the number of additions at each position

Concrete Example

For \(N = 5\) plants, watering the interval \([2, 4]\):

diff:        [0, +1, 0, 0, -1, 0]  (index 1 gets +1, index 5 gets -1)
prefix sum:  [0,  1, 1, 1,  0, 0]  (positions 2, 3, 4 are incremented by +1)

Application Steps for This Problem

1. Prepare a difference array diff of length \(N+1\)
2. For each watering operation \((L_j, R_j)\), set diff[L_j-1] += 1 and diff[R_j] -= 1 (converting to 0-indexed)
3. While computing the prefix sum of diff, count the plants where \(A_i + \text{watering count} \geq K\)

Complexity

• Time complexity: \(O(N + M)\)
  • Recording each watering operation: \(O(M)\) (\(O(1)\) per operation)
  • Computing the prefix sum and counting: \(O(N)\)
• Space complexity: \(O(N)\)
  • \(O(N)\) for the difference array diff

Implementation Notes

1. Index conversion: The problem uses 1-indexed notation, but Python arrays are 0-indexed. Use L-1 and R to convert appropriately.

2. Size of the difference array: The length of diff must be \(N+1\). This is because when \(R = N\), we need to write to diff[R].

3. Overflow prevention: Although \(A_i\) and \(K\) can be up to \(10^9\), Python handles arbitrary-precision integers, so there is no concern about overflow.

4. Simultaneous prefix sum and evaluation: By performing the condition check while computing the prefix sum, we can process efficiently without creating an extra array.

   Source Code

def main():
    import sys
    input = sys.stdin.readline
    
    N, M, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # いもす法を使用して区間加算を効率的に処理
    # diff[i] は位置 i での増分の変化量
    diff = [0] * (N + 1)
    
    for _ in range(M):
        L, R = map(int, input().split())
        # 1-indexed を 0-indexed に変換
        diff[L - 1] += 1
        diff[R] -= 1
    
    # 累積和を取って各位置での水やり回数を計算
    water_count = 0
    result = 0
    
    for i in range(N):
        water_count += diff[i]
        if A[i] + water_count >= K:
            result += 1
    
    print(result)

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.