Overview

The range that can be watered by the sprinkler is a half-open interval \([s, s+D)\) of length \(D\).
We want to maximize the number of flowers contained in this interval, and subtract it from the total number of flowers to find the minimum number of flowers that cannot be watered.

Observation

When the sprinkler is placed at coordinate \(s\), the flowerbeds that can be watered are those where \(X_i\) satisfies:

\(s \leq X_i < s+D\)

In other words, the problem can be rephrased as follows:

There are weights \(P_i\) at points \(X_i\) on a number line.
Find the maximum sum of weights contained in an interval \([s, s+D)\) of length \(D\).

If we denote the total number of flowers as \(\text{total}\) and the maximum number of flowers that can be watered as \(\text{best}\), the answer is:

\(\text{total} - \text{best}\)

Here is an important observation:

Although the starting position \(s\) of the sprinkler can be any real number, it is sufficient to consider only the cases where the left end of the optimal interval is aligned with the coordinate of some flowerbed \(X_l\).

This is because, suppose there are flowerbeds watered in a certain interval \([s, s+D)\). Let \(X_l\) be the coordinate of the leftmost flowerbed among them.

In this case, even if we shift the left end of the interval to the right up to \(X_l\), resulting in \([X_l, X_l+D)\), all the flowerbeds that were originally watered will still be included.

Therefore, for each \(l\), it is sufficient to examine the number of flowers contained in:

\([X_l, X_l+D)\)

A naive search for the right end for each \(l\) would take \(O(N^2)\) time in the worst case.
Since \(N \leq 2 \times 10^5\), this will exceed the time limit.

Thus, we can use the two-pointer approach to find this efficiently, taking advantage of the fact that the coordinates \(X_i\) are sorted in ascending order.

Algorithm

We use the two-pointer approach.

Let \(l\) be the index of the leftmost flowerbed, and \(r\) be the index representing the right end. We manage the interval as a half-open interval:

\([l, r)\)

such that the flowerbeds contained in it satisfy the coordinate range:

\(X_l \leq X_i < X_l + D\)

The procedure is as follows:

1. Calculate the total number of flowers, \(\text{total}\).
2. Iterate \(l\) from \(0\) to \(N-1\).
3. While \(X_r < X_l + D\), advance \(r\) to the right and add the number of flowers.
4. Update \(\text{best}\) with the number of flowers in the current interval.
5. To proceed to the next \(l\), subtract the current leftmost value \(P_l\) from the interval sum.
6. Finally, print \(\text{total} - \text{best}\).

For example, when the current left end is \(X_l\), the condition is:

\(X_i < X_l + D\)

In the problem statement, the right end is “less than distance \(D\)”, so the flowerbed at \(X_i = X_l + D\) is not included. Therefore, the condition uses < instead of <=.

Complexity

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

Each index \(l\) is incremented \(N\) times, and \(r\) also advances at most \(N\) times in total, making the overall two-pointer approach run in \(O(N)\) time.

Key Implementation Points

The number of flowers \(P_i\) is up to \(10^9\), and \(N\) is up to \(2 \times 10^5\). The sum can be at most:

\(2 \times 10^5 \times 10^9 = 2 \times 10^{14}\)

which means we need to use long long instead of int.

Also, since the watering range is \([s, s+D)\), the check for the right end should be:

X[r] < X[l] + D

If you write X[r] <= X[l] + D, it would include the flowerbed at exactly distance \(D\), which leads to an incorrect answer.

Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long D;
    cin >> N >> D;

    vector<long long> X(N), P(N);
    for (int i = 0; i < N; i++) {
        cin >> X[i] >> P[i];
    }

    long long total = 0;
    for (long long p : P) total += p;

    long long best = 0;
    long long sum = 0;
    int r = 0;

    for (int l = 0; l < N; l++) {
        while (r < N && X[r] < X[l] + D) {
            sum += P[r];
            r++;
        }
        best = max(best, sum);
        sum -= P[l];
    }

    cout << total - best << '\n';

    return 0;
}

---

This editorial was generated by gpt-5.5-high.