Overview

Given \(N\) plants, we perform \(M\) operations of “increase the water amount of all plants in the range \([L, R]\) by \(1\)”. The problem asks us to find the number of plants whose final water amount is at least the threshold \(K\).

Analysis

Naive Approach

What happens if, for each watering operation, we loop through all plants from \(L\) to \(R\) and increment their water amounts? In the worst case, a single operation waters all \(N\) plants, and this is repeated \(M\) times, resulting in a time complexity of \(O(N \times M)\). Given the constraints of this problem, \(N, M \leq 2 \times 10^5\), this would require up to about \(4 \times 10^{10}\) computations, which will not fit within the time limit (TLE).

Efficient Approach (Imos Method)

To speed up the operation of “adding a uniform value to a specific range,” we use a technique called the “Imos method (difference array)”. In the Imos method, the operation of adding \(1\) to the range \([L, R]\) is represented by updates to just the following two points: 1. Add \(+1\) at the start point \(L\) (the increase begins here) 2. Add \(-1\) at the position after the end point \(R+1\) (the increase ends here)

After all operations are complete, by taking the prefix sum from the beginning of the array, we can determine the total amount added at each position in \(O(N)\). This allows us to solve the entire problem with a time complexity of \(O(N + M)\).

Algorithm

1. Prepare the difference array: Initialize an array diff of length \(N+2\) with \(0\) (to account for 1-indexed management and access to \(R+1\)).
2. Record watering operations: For each of the \(M\) watering operations \((L_j, R_j)\), do the following:
   • diff[L_j] += 1
   • diff[R_j + 1] -= 1
3. Prefix sum and evaluation:
   • Initialize a variable current_water (current cumulative addition) to \(0\).
   • Iterate through plants \(i = 1\) to \(N\) in order:
     • Update current_water += diff[i].
     • The final water amount of plant \(i\) is A[i] + current_water.
     • If this is at least \(K\), increment the answer count by \(1\).

Complexity

• Time complexity: \(O(N + M)\)
  • Reading input takes \(O(N + M)\), recording watering operations takes \(O(M)\), and computing the prefix sum and evaluation takes \(O(N)\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to maintain the array of initial plant values and the difference array.

Implementation Notes

• Fast I/O: Since \(N\) and \(M\) can be large, in Python it is faster to read all input at once using sys.stdin.read().split() rather than repeatedly calling input().

• Index management: The problem statement is 1-indexed (plant numbers start from 1), but care must be taken with array handling within the program and the boundary condition at \(R+1\) to ensure the array size is sufficient. In this code, we allocate a size of \(N + 2\) to prevent out-of-bounds access.

  Source Code

import sys

def solve():
    # Fast input reading: read the entire input and split by whitespace
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: number of plants, M: number of watering operations, K: threshold
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    # A: initial moisture levels for plants 1 to N
    # Using list(map(int, ...)) on a slice is efficient in Python
    A = list(map(int, input_data[3 : 3 + N]))
    
    # diff: difference array for the imos method (range updates)
    # diff[i] stores the change in moisture level starting at plant i.
    # Size N + 2 is used to handle 1-based indexing and the boundary at R + 1.
    diff = [0] * (N + 2)
    
    # Process M watering operations
    # Each operation is given as a range [L, R]
    idx = 3 + N
    for _ in range(M):
        L = int(input_data[idx])
        R = int(input_data[idx + 1])
        # Increment water level at index L, decrement after index R
        diff[L] += 1
        diff[R + 1] -= 1
        idx += 2
        
    # ans_count: number of plants whose final moisture level is at least K
    ans_count = 0
    # current_water: cumulative water added to the plant currently being evaluated
    current_water = 0
    
    # Evaluate each plant from 1 to N
    for i in range(N):
        # Update the cumulative water using the difference array
        # A[i] corresponds to plant i+1, so we look at diff[i+1]
        current_water += diff[i + 1]
        # Final moisture = initial moisture + total water added
        if A[i] + current_water >= K:
            ans_count += 1
            
    # Output the final result to standard output
    sys.stdout.write(str(ans_count) + '\n')

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.