Overview

This problem asks us to determine the number of flowers whose final dryness level is at most a threshold \(T\), after performing \(M\) interval watering operations (decreasing dryness) on \(N\) flowers arranged in a row. By mathematically reformulating the constraint “dryness does not go below \(0\)” and using the difference array technique (imos method), we can solve this efficiently within the time limit.

Analysis

1. Limitations of Naive Simulation

Consider the straightforward approach of updating each element one by one in the specified interval \([L_j, R_j]\) for each watering operation. In this case, a single watering operation may update up to \(N\) elements, resulting in an overall time complexity of \(O(NM)\). Given the constraints \(N \leq 5 \times 10^5\) and \(M \leq 2 \times 10^5\), the worst case requires approximately \(10^{11}\) operations, which will not finish within the time limit (TLE).

2. Reformulating the Constraint “Dryness Does Not Go Below \(0\)”

The problem states that “dryness does not go below \(0\).” At first glance, it seems like we need to check and handle whether each flower’s dryness reaches \(0\) after every watering operation.

However, if we focus only on the final state, this constraint can be reformulated very simply. Let \(S_i\) be the total decrease applied to flower \(i\) across all \(M\) watering operations. Considering that the dryness is prevented from going below \(0\) during the process, the final dryness can be expressed as \(\max(F_i - S_i, 0)\).

What we want to know is whether the final dryness is at most \(T\) (i.e., \(\max(F_i - S_i, 0) \leq T\)). Since \(T \geq 0\), this inequality can be transformed as follows:

\[ \max(F_i - S_i, 0) \leq T \iff F_i - S_i \leq T \iff S_i \geq F_i - T \]

In other words, we do not need to track whether the dryness “went below \(0\)” at each intermediate step. We only need to determine whether the final total decrease \(S_i\) is at least \(F_i - T\).

3. Speeding Up Range Addition with the Imos Method

The problem has been reduced to: “For each query \((L_j, R_j, D_j)\), add \(D_j\) uniformly to the interval \([L_j, R_j]\), and compute the final sum \(S_i\) at each position.” This can be processed using the difference array technique (imos method) in \(O(1)\) per query, with an overall time complexity of \(O(N + M)\).

Algorithm

1. Prepare the difference array: Initialize an array diff of length \(N+2\) with all zeros.

2. Process queries (imos method): For each watering query \((L_j, R_j, D_j)\), perform the following additions:

   • diff[L_j] += D_j
   • diff[R_j + 1] -= D_j

3. Compute prefix sums and make judgments: By computing the prefix sum of the array diff from left to right, we recover the total decrease \(S_i\) for each flower \(i\). For \(i = 1, 2, \ldots, N\), do the following in order:

   • \(S_i = S_{i-1} + \text{diff}[i]\)
   • If \(S_i \geq F_i - T\) is satisfied, that flower is in a “healthy state,” so increment the answer count by \(1\).

Complexity

• Time Complexity: \(O(N + M)\)

  • Processing \(M\) queries takes \(O(M)\) time.
  • Computing prefix sums and checking conditions takes \(O(N)\) time.
  • Overall, this is \(O(N + M)\), which comfortably fits within the time limit.

• Space Complexity: \(O(N)\)

  • \(O(N)\) memory is used for the array \(F\) storing initial dryness values and the difference array diff.

Implementation Notes

• Fast I/O: In Python, when the number of input lines is large, the overhead of calling input() many times increases execution time. By using sys.stdin.read().split() to read all input at once and parsing it in memory, we can achieve a significant speedup.

• Handling 1-indexed arrays: Since flower numbers start from \(1\), we set the array size to \(N+2\) and insert a dummy element (0) at the beginning of the initial dryness array \(F\) to prevent off-by-one bugs caused by index shifting.

  Source Code

import sys


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    M = int(input_data[1])
    T = int(input_data[2])

    F = [0] + [int(x) for x in input_data[3 : 3 + N]]

    diff = [0] * (N + 2)
    idx = 3 + N
    for _ in range(M):
        L = int(input_data[idx])
        R = int(input_data[idx + 1])
        D = int(input_data[idx + 2])
        diff[L] += D
        diff[R + 1] -= D
        idx += 3

    ans = 0
    current = 0
    for i in range(1, N + 1):
        current += diff[i]
        if current >= F[i] - T:
            ans += 1

    print(ans)


if __name__ == "__main__":
    solve()

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