Overview

This problem asks us to place an interval of length \(D\) (specifically, a half-open interval \([s, s+D)\)) on a number line with \(N\) shrubs to maximize the total number of watered flowers. The “minimum number of unwatered flowers” can be found by subtracting the “maximum number of watered (covered) flowers” from the “total number of all flowers.”

Analysis

1. Narrowing Down the Candidate Positions for the Sprinkler

Although the sprinkler’s starting position \(s\) can be any non-negative real number, it is impossible to search all infinitely many real numbers. Therefore, let us consider the properties of an optimal placement.

Suppose some shrubs are contained within a range \([s, s+D)\). If we move the sprinkler’s position \(s\) to the right, there will be a moment just before one of the shrubs falls out of the left end, which is the exact moment when \(s\) coincides with the coordinate \(X_l\) of some shrub. By aligning the left end of the sprinkler exactly with the coordinate of a shrub \(X_l\) (setting \(s = X_l\)), we can cover the leftmost shrub while extending the right end as far to the right as possible.

Therefore, it is sufficient to consider only the cases where the sprinkler’s starting position \(s\) coincides with the coordinate of some shrub \(X_l\) (\(1 \leq l \leq N\)).

2. Naive Approach and Its Issues

When we set each shrub \(l\) as the left end, the right end \(r\) is the largest shrub index satisfying \(X_r < X_l + D\). What happens if we calculate the sum of the flowers in this range \([l, r]\) for each \(l\) individually?

Finding \(r\) and calculating the sum for a single \(l\) takes \(O(N)\) time, resulting in an overall time complexity of \(O(N^2)\). Since the constraint of this problem is \(N \leq 2 \times 10^5\), this approach will not run within the time limit (resulting in TLE).

3. Optimization using Two Pointers

Here, note that the coordinates of the shrubs are sorted in ascending order: \(X_1 < X_2 < \cdots < X_N\). When we move the left end \(l\) to the right, the right end \(r\) that satisfies the condition \(X_r < X_l + D\) also only moves to the right and never moves back to the left (monotonicity).

Using this property, we can apply the Two Pointers technique. By advancing the left end \(l\) one by one, moving the right end \(r\) to the right as long as the condition is satisfied, and updating the total number of flowers in the interval incrementally, we can efficiently find the maximum value for each \(l\).

Algorithm

1. Initialization:

   • Calculate the total number of all flowers, total_P.
   • Initialize the variable current_sum (representing the sum of flowers in the current interval) and max_covered (representing its maximum value) to \(0\).
   • Set the pointer r pointing to the right end to \(0\).

2. Two Pointers Method:

   • Increment the left end index l from \(0\) to \(N-1\).
   • While r is less than \(N\) and satisfies \(X_r < X_l + D\), add \(P_r\) to current_sum and increment r by \(1\).
   • Once the condition is no longer met, compare the current current_sum with max_covered and update the maximum value.
   • Before moving to the next l, subtract the number of flowers at the current left end \(P_l\) from current_sum.

3. Outputting the Answer:

   • total_P - max_covered will be the minimum number of unwatered flowers.

Complexity

• Time Complexity: \(O(N)\)
  • Each of l and r increases from \(0\) to \(N\) at most once. Therefore, the total number of transitions in the two pointers loop is at most \(2N\), allowing the process to be completed in \(O(N)\) time complexity overall.
• Space Complexity: \(O(N)\)
  • Only the memory for the arrays to store the input coordinates \(X\) and the number of flowers \(P\) is required.

Implementation Points

• Preventing Overflow:

  • The number of flowers \(P_i\) is up to \(10^9\), and the number of shrubs \(N\) is up to \(2 \times 10^5\). Since the total number of flowers can reach up to \(2 \times 10^{14}\), standard 32-bit integer types (such as int in C++) will overflow. Make sure to use 64-bit integer types (such as long long in C++) for variables handling sums (total_P, current_sum, max_covered).

• Half-Open Interval Condition:

  • The sprinkler’s watering range is \(s \leq X_i < s + D\) (strictly less than \(s+D\)). Therefore, the continuation condition for the two pointers method is X[r] < X[l] + D, and you must be careful not to include the equals sign.

    Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long D;
    if (!(cin >> N >> D)) return 0;

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

    long long max_covered = 0;
    int r = 0;
    long long current_sum = 0;

    // しゃくとり法により、各左端 l に対してカバーできる最大の右端 r を求める
    for (int l = 0; l < N; ++l) {
        while (r < N && X[r] < X[l] + D) {
            current_sum += P[r];
            r++;
        }
        max_covered = max(max_covered, current_sum);
        current_sum -= P[l];
    }

    long long ans = total_P - max_covered;
    cout << ans << "\n";

    return 0;
}

---

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