Overview

This problem asks you to find the number of elements whose final value falls below a specific threshold after repeatedly performing subtraction operations on multiple intervals. Although the conditions appear complex at first glance, by organizing the properties of the problem, we can reduce it to a fast \(O(N + M)\) algorithm using the difference array technique (prefix sums).

Analysis

Naive Approach and Its Limitations

One could consider updating the dryness for all flowers in the specified interval \([L_j, R_j]\) for each watering query. However, this method requires up to \(O(N)\) computation per watering operation, resulting in \(O(NM)\) total time. In this problem, since \(N \le 5 \times 10^5\) and \(M \le 2 \times 10^5\), this would require approximately \(10^{11}\) operations, which would exceed the time limit (TLE).

To speed things up, we need to consider a method that efficiently handles interval addition (subtraction).

Key Insight: Simplifying the “Dryness Cannot Go Below \(0\)” Rule

The problem states that “dryness cannot go below \(0\) (it is updated to \(\max(v - D_j, 0)\)).” At first glance, it seems like we need to explicitly track “whether the value reached \(0\) at each step” because of this rule.

However, the ultimate goal is to determine “whether the final dryness is at most \(T\).” Let \(S_i\) be the total sum of all decreases from watering applied to flower \(i\). Then, by completely ignoring the intermediate clamping at \(0\), we can simply check whether \(S_i \ge F_i - T\) to obtain the correct result.

This is because the threshold \(T\) is non-negative (\(T \ge 0\)), so we can consider the following two cases:

1. When \(S_i \ge F_i - T\):

   • If the dryness reached \(0\) during watering, the final dryness becomes \(0\). Since \(T \ge 0\), the final dryness of \(0\) is at most \(T\).
   • If the dryness never reached \(0\) during watering, the final dryness is exactly \(F_i - S_i\), which is at most \(T\).
   • Therefore, in either case, the final dryness is at most \(T\).

2. When \(S_i < F_i - T\):

   • Since \(T \ge 0\), we have \(S_i < F_i\). Because the total decrease is less than the initial value, the dryness never reaches \(0\) during the process.
   • Therefore, the final dryness is exactly \(F_i - S_i\), which is greater than \(T\).

From this analysis, we see that we do not need to worry about the complex constraint “the value cannot go below \(0\).” Instead, we only need to determine “whether the total decrease \(S_i\) for each flower \(i\) is at least \(F_i - T\).”

Speeding Up Interval Addition (Difference Array Technique)

The operation of “adding value \(D_j\) to multiple intervals \([L_j, R_j]\) and finding the final sum at each position” can be performed very efficiently using the difference array technique (imos method).

Prepare a difference array diff of length \(N+2\), and for each query \((L_j, R_j, D_j)\), perform: - diff[L_j] += D_j - diff[R_j + 1] -= D_j

in \(O(1)\) time. After processing all queries, by computing the prefix sum from left to right, we can obtain the total decrease \(S_i\) for each flower \(i\) all at once in \(O(N)\).

Algorithm

1. Initialize a difference array diff of length \(N+2\) with \(0\).
2. For each query \((L_j, R_j, D_j)\), perform diff[L_j] += D_j and diff[R_j + 1] -= D_j.
3. Compute the prefix sum of the difference array from left to right. The prefix sum at position \(i\) equals the total decrease \(S_i\) for flower \(i\).
4. If \(S_i \ge F_i - T\) is satisfied, that flower is in a “healthy state,” so increment the answer count by \(1\).
5. Output the final count.

Complexity

• Time Complexity: \(O(N + M)\)
  • Processing the queries takes \(O(M)\), and computing the prefix sum and checking the condition takes \(O(N)\). Since the algorithm runs in linear time overall, it comfortably fits within the time limit.
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the initial dryness array \(F\) and the difference array diff.

Implementation Notes

• Preventing Overflow The initial dryness values \(F_i\) and decrease amounts \(D_j\) can be up to \(10^9\), and the prefix sum \(S_i\) can reach up to \(M \times \max(D_j) = 2 \times 10^{14}\). This would overflow a 32-bit integer type (int), so be sure to use a 64-bit integer type (long long in C++) for the variable holding the prefix sum and for the difference array.

• Array Boundaries Since the difference array technique accesses index R_j + 1, the array size must be at least \(N + 2\). Implementing with 1-based indexing makes it intuitive and safely prevents out-of-bounds access.

  Source Code

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    long long T;
    if (!(cin >> N >> M >> T)) return 0;

    vector<long long> F(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> F[i];
    }

    vector<long long> diff(N + 2, 0);
    for (int j = 0; j < M; ++j) {
        int L, R;
        long long D;
        cin >> L >> R >> D;
        diff[L] += D;
        diff[R + 1] -= D;
    }

    int ans = 0;
    long long current_S = 0;
    for (int i = 1; i <= N; ++i) {
        current_S += diff[i];
        if (current_S >= F[i] - T) {
            ans++;
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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