Overview

This problem asks you to find the minimum total construction cost when selecting 2 candidate locations whose coordinates are within \(D\) of each other (output -1 if no such pair exists).

Analysis

The condition is: “When the selected relay stations are arranged in coordinate order, all adjacent distances must be at most \(D\).”

The key insight is as follows:

• All construction costs \(C_i\) are positive (\(C_i \ge 1\))
• Therefore, selecting 3 or more relay stations will always increase the total cost

Thus, if a valid selection exists, the minimum cost is always achieved with \(k=2\) (installing at exactly 2 locations).
In this case, the condition is simply:

• The distance between the two points is at most \(D\): \(|X_a - X_b| \le D\)

So the problem reduces to:

Among all pairs with distance at most \(D\), find the minimum value of \(C_a + C_b\)

Naively checking all pairs is \(O(N^2)\), which is too slow for \(N \le 2\times 10^5\).
Instead, we “sort by coordinate” and for each point, efficiently find “the minimum cost among previous points within distance \(D\).”

Algorithm

1. Receive the candidate locations as \((X_i, C_i)\) and sort them in ascending order of coordinate \(X\).
2. Using a left pointer \(l\), for each \(i\):
   • Maintain “the smallest \(l\) such that \(X_i - X_l \le D\)” (the range of points within \(D\) of \(X_i\) is \([l, i-1]\)).
3. If we can retrieve the minimum cost among points in the range \([l, i-1]\), the best pair candidate is:
   • \(\text{minCostInWindow} + C_i\)
4. Use a heap (priority queue) to manage the minimum cost.
   • Store (C[j], j) in the heap
   • Elements that have moved left of \(l\) (out of range) are discarded when they reach the top of the heap (lazy deletion)

Flow (operations for each \(i\)): - While \(X_i - X_l > D\), advance \(l\) to the right - If the index at the top of the heap is less than \(l\), pop it (discard since it’s out of range) - If the heap is not empty, ans = min(ans, C[i] + heap_min_cost) - Finally, push (C[i], i) onto the heap

This allows us to efficiently obtain “the minimum cost among partners within distance \(D\)” at all times.

Complexity

• Time complexity: \(O(N \log N)\) (sorting \(O(N\log N)\) + each element is pushed/popped at most once)
• Space complexity: \(O(N)\) (at most \(N\) elements in the heap)

Implementation Notes

• Without sorting by coordinate, we cannot treat “past elements within distance \(D\)” as a contiguous interval, making optimization impossible.

• Since direct deletion from a heap is not possible, lazy deletion — popping while heap[0][1] < l — is essential.

• If the answer is never updated (no valid pair is found), output -1.

  Source Code

import sys
import heapq

def main():
    input = sys.stdin.readline
    N, D = map(int, input().split())
    pts = [tuple(map(int, input().split())) for _ in range(N)]  # (X, C)
    pts.sort()
    X = [p[0] for p in pts]
    C = [p[1] for p in pts]

    INF = 10**30
    ans = INF

    heap = []  # (cost, index)
    l = 0

    for i in range(N):
        while l < i and X[i] - X[l] > D:
            l += 1
        while heap and heap[0][1] < l:
            heapq.heappop(heap)

        if heap:
            ans = min(ans, C[i] + heap[0][0])

        heapq.heappush(heap, (C[i], i))

    print(-1 if ans == INF else ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.