Overview

Each village where a radio tower can be placed (elevation \(P_i \ge K\)) creates an “interval covering within distance \(D\),” so the problem asks for the minimum number of intervals needed to cover all village positions \(X_i\) (points) with those intervals. If any point cannot be covered, the answer is -1.

Analysis

Key Observation: One Radio Tower = One Interval

When a tower is placed at village \(i\) that satisfies the elevation condition, the signal covers a radius of \(D\) centered at position \(X_i\), so the coverage range is:

• Interval \([X_i - D,\; X_i + D]\)

Therefore, the problem can be rephrased as follows:

• Cover all points (all village positions \(X_i\)) using selectable intervals (intervals created by villages satisfying the elevation condition)
• Minimize the number of intervals used

Why a Naive Solution Is Difficult

• “Which villages to place towers at” involves choosing from up to \(2 \times 10^5\) candidates, making exhaustive search impossible.
• Naively finding “all covering intervals for each point” easily becomes \(O(N^2)\), resulting in TLE.

How to Solve It: Greedy from Left to Right

We look at points (village positions) from left to right, and for each “leftmost uncovered point,” among the intervals that can cover it, we choose:

• The interval whose right endpoint extends the farthest to the right

This is optimal. It is the classic greedy algorithm for the “minimum number of intervals to cover points” problem.

Why Does This Give the Minimum?

To cover the leftmost uncovered point \(cur\), we must choose at least one interval whose left endpoint is at most \(cur\).
Among those, choosing the one with the farthest right endpoint maximizes the number of future points that get covered, working toward reducing the total number of intervals.
(If we choose an interval with a shorter right endpoint, even though it covers the same \(cur\), we cannot advance as far, requiring extra intervals later.)

Algorithm

1. Sort villages by position \(X\) to create a point sequence \(x_0 < x_1 < \dots\).
2. From only villages with elevation \(P_i \ge K\), create intervals \([X_i-D,\; X_i+D]\), collect them, and sort by left endpoint.
3. Sweep from left to right, tracking the “leftmost uncovered point” \(cur\):
   • Add all intervals whose left endpoint is at most \(cur\) to the candidate pool (priority queue).
   • From those candidates, select the interval with the maximum right endpoint (= install one tower).
   • Skip all points that are at most the right endpoint \(end\) of that interval, marking them as “covered.”
   • If the candidate pool is empty, that point cannot be covered, so output -1.
4. If all points are covered, output the number of selected intervals (number of towers).

Implementation Detail (Priority Queue)

• To efficiently extract the “maximum right endpoint,” we insert -end into Python’s heapq (min-heap) to use it as a max-heap.
• After selecting one interval, the code does heap.clear().
  This is safe because the selected interval has the maximum right endpoint among all intervals with starting position \(\le cur\), so all remaining candidates have right endpoints no greater than the selected one, and they are useless for covering the next uncovered point (which is to the right of \(end\)), so they can be safely discarded.

Complexity

• Time complexity: \(O(N \log N)\)
  (Sorting \(O(N \log N)\) + total heap operations \(O(N \log N)\))
• Space complexity: \(O(N)\)
  (Interval array and heap)

Implementation Notes

• Positions \(X_i\) must be sorted (not kept in input order) to establish the “cover from left to right” state.

• If no village satisfies the elevation condition \(P_i \ge K\), immediately output -1.

• During the sweep, if “no candidate intervals exist” = that point cannot be covered, so output -1.

• Since heapq is a min-heap, to extract the maximum value, insert with the sign flipped (-end).

  Source Code

import sys
import heapq

def main():
    input = sys.stdin.buffer.readline
    N, K, D = map(int, input().split())
    villages = [tuple(map(int, input().split())) for _ in range(N)]
    villages.sort()  # sort by X

    xs = [x for x, _ in villages]

    intervals = []
    for x, p in villages:
        if p >= K:
            intervals.append((x - D, x + D))
    if not intervals:
        print(-1)
        return

    intervals.sort()
    m = len(intervals)

    t = 0  # index over villages (points to cover)
    i = 0  # index over intervals
    heap = []  # max-heap of ends (store -end)
    ans = 0

    while t < N:
        cur = xs[t]

        while i < m and intervals[i][0] <= cur:
            heapq.heappush(heap, -intervals[i][1])
            i += 1

        if not heap:
            print(-1)
            return

        end = -heapq.heappop(heap)
        if end < cur:
            print(-1)
            return

        ans += 1
        heap.clear()

        while t < N and xs[t] <= end:
            t += 1

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.