Overview

This problem requires sorting candidate locations in ascending order of coordinates, then efficiently finding the minimum cost of installing two or more relay stations using dynamic programming (DP) and a segment tree, while satisfying the condition that the distance between adjacent relay stations is at most \(D\).

Analysis

First, there is a condition that when relay stations are arranged in ascending order of coordinates, the distance between adjacent ones must be at most \(D\). Since coordinates are given in an arbitrary order, it is natural to first sort them in ascending order of \(X_i\). Let the sorted locations be \(0, 1, \ldots, N-1\).

When selecting relay stations to satisfy the condition, suppose the last selected relay station is at location \(i\). Then, if the previously selected relay station is at location \(j\) (\(j < i\)), the condition requires \(X_i - X_j \le D\), i.e., \(X_j \ge X_i - D\). Additionally, at least 2 relay stations must be installed.

We define the following dynamic programming (DP): - \(dp[i]\): The minimum construction cost when location \(i\) is the last selected relay station (and at least 2 locations are selected in total)

Let \(j\) be the relay station selected immediately before location \(i\). \(j\) must satisfy the following conditions: - \(j < i\) - \(X_j \ge X_i - D\)

The transition from location \(j\) to location \(i\) falls into one of the following two patterns: 1. Location \(j\) was the “first station”: Location \(i\) becomes the second station, and the cost is \(C_j + C_i\). 2. Location \(j\) was already the “second or later station”: Including location \(i\), the condition of having at least 2 stations is satisfied, and the cost is \(dp[j] + C_i\).

Therefore, the transition to location \(i\) is: $\(dp[i] = C_i + \min_{j: X_i - D \le X_j < X_i} \min(C_j, dp[j])\)$

If we compute this transition naively, searching for \(j\) for each \(i\) takes \(O(N)\) in the worst case, resulting in an overall time complexity of \(O(N^2)\). Since \(N \le 2 \times 10^5\), this would not fit within the time limit (TLE).

To speed this up, the following two optimizations are needed: 1. Quickly determine the range \([L, i)\) of source indices \(j\) for the transition. 2. Quickly obtain the minimum value of \(\min(C_j, dp[j])\) within that range.

For 1, since the coordinates are sorted, we can use binary search (std::lower_bound) to find the smallest index \(L\) satisfying \(X_L \ge X_i - D\) in \(O(\log N)\). For 2, by using a Segment Tree, a data structure that efficiently retrieves the minimum value over an interval, we can obtain the minimum value over the interval \([L, i)\) in \(O(\log N)\).

Algorithm

1. Sort: Sort all candidate locations in ascending order of coordinate \(X_i\).
2. Initialization:
   • Prepare a DP array \(dp\) of size \(N\) with initial value \(\infty\) (a sufficiently large value).
   • Prepare a segment tree seg of size \(N\) with initial value \(\infty\) that can retrieve interval minimum values.
3. DP Transition: For \(i = 0\) to \(N-1\), perform the following:
   • Using binary search, find the smallest index \(L\) satisfying \(X_j \ge X_i - D\).
   • If \(L < i\), retrieve the minimum value \(M = \min_{L \le j < i} \min(C_j, dp[j])\) from the segment tree over the interval \([L, i)\).
   • If \(M < \infty\), update \(dp[i] = C_i + M\).
   • Register (set) \(\min(C_i, dp[i])\) at position \(i\) in the segment tree.
4. Output the Answer: \(\min_{0 \le i < N} dp[i]\) is the desired minimum cost. If it remains \(\infty\), there is no valid selection satisfying the conditions, so output -1.

Complexity

• Time Complexity: \(O(N \log N)\)
  • Sorting the coordinates takes \(O(N \log N)\).
  • For each \(i\), the binary search takes \(O(\log N)\), and the segment tree query and update take \(O(\log N)\), so the entire DP transition takes \(O(N \log N)\).
  • Therefore, the overall time complexity is \(O(N \log N)\), which runs sufficiently fast within the constraints.
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used to store coordinates, costs, the DP array, and the segment tree.

Implementation Notes

• Unified Management of First and Subsequent Stations: By registering \(\min(C_i, dp[i])\) in the segment tree, we can manage both “the case where the station is selected as the first one (\(C_i\))” and “the case where at least 2 stations have already been selected (\(dp[i]\))” within the same segment tree, making the transition code very simple.

• Index Retrieval: Converting the iterator obtained from binary search to index \(L\) can be done in \(O(1)\) using std::distance(X.begin(), it).

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <atcoder/segtree>

using namespace std;
using namespace atcoder;

const long long INF = 1LL << 60;

long long op(long long a, long long b) {
    return min(a, b);
}

long long e() {
    return INF;
}

struct Point {
    long long x;
    long long c;
    bool operator<(const Point& other) const {
        return x < other.x;
    }
};

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

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

    vector<Point> points(N);
    for (int i = 0; i < N; ++i) {
        cin >> points[i].x >> points[i].c;
    }

    sort(points.begin(), points.end());

    vector<long long> X(N);
    for (int i = 0; i < N; ++i) {
        X[i] = points[i].x;
    }

    segtree<long long, op, e> seg(N);
    vector<long long> dp(N, INF);

    for (int i = 0; i < N; ++i) {
        long long target = X[i] - D;
        auto it = lower_bound(X.begin(), X.end(), target);
        int L = distance(X.begin(), it);

        if (L < i) {
            long long min_val = seg.prod(L, i);
            if (min_val < INF) {
                dp[i] = points[i].c + min_val;
            }
        }
        seg.set(i, min(points[i].c, dp[i]));
    }

    long long ans = INF;
    for (int i = 0; i < N; ++i) {
        ans = min(ans, dp[i]);
    }

    if (ans >= INF) {
        cout << -1 << "\n";
    } else {
        cout << ans << "\n";
    }

    return 0;
}

---

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