Overview

The initial moisture levels of plants are given, and through multiple watering operations, the moisture levels of plants in specified ranges increase. The problem asks us to find the number of plants whose final moisture level is at least \(K\).

Analysis

In a naive approach, for each watering operation, we would directly add +1 to every plant in the specified range. In the worst case, each watering covers nearly the entire range, resulting in a time complexity of \(O(N \times M)\). Since \(N, M\) can be up to 200,000, this would require up to \(4 \times 10^{10}\) operations, which exceeds the time limit.

To solve this problem efficiently, we need a method that can perform range updates quickly. Here, by using an algorithm called “imos method” (difference array technique), we can record range updates in constant time and compute the results all at once at the end.

Algorithm

1. Create a difference array: Create an array diff of length \(N+1\) (0-indexed)
2. Query processing: For each watering query \((L_j, R_j)\):
   • diff[L] += 1 (start position of the range)
   • diff[R+1] -= 1 (position right after the end of the range)
3. Compute prefix sums: By computing the prefix sum of the difference array, we obtain the number of times each plant was watered
4. Evaluation: For each plant \(i\), add the number of waterings to the initial value \(A_i\), and check whether it is at least \(K\), counting those that satisfy the condition

With this method, processing \(M\) queries takes \(O(1)\) each, and computing the prefix sum takes \(O(N)\), so the overall computation runs efficiently in \(O(N + M)\).

Complexity

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

Implementation Notes

• Pay attention to array indexing: the problem uses 1-indexed values, but the code processes them as 0-indexed

• By setting the size of the difference array to \(N+1\), we prevent \(R+1\) from going out of bounds

• When computing the prefix sum, use a variable current to maintain the running total, adding the difference value at each position as we process

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    it = iter(data)
    N = int(next(it)); M = int(next(it)); K = int(next(it))
    A = [int(next(it)) for _ in range(N)]
    queries = []
    for _ in range(M):
        L = int(next(it)) - 1
        R = int(next(it)) - 1
        queries.append((L, R))
    
    diff = [0] * (N + 1)
    for L, R in queries:
        diff[L] += 1
        diff[R + 1] -= 1
    
    count = 0
    current = 0
    for i in range(N):
        current += diff[i]
        if A[i] + current >= K:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.