Overview

Given villages lined up along a single road, the problem asks to place the minimum number of radio towers at locations satisfying an altitude condition so that all villages are covered. By leveraging the property that villages are arranged on a straight line, we can solve this using a Greedy Algorithm that determines optimal positions sequentially from one end.

Analysis

1. Which village should we consider first?

Since all villages must be covered, we focus on the leftmost village among those not yet covered. To cover this village, at least one radio tower must be placed within distance \(D\) from it.

2. Where is the optimal place to put a radio tower?

When placing a radio tower to cover a certain village (at position \(x\)), it is best for minimizing the total number of towers to position the tower so that it also covers as many villages to the right as possible. A radio tower covers a range of \(D\) in both directions from its installation point. Therefore, within the range \([x - D, x + D]\) that can cover the village at position \(x\), the most efficient choice is to place the tower at the village that has altitude \(K\) or higher AND is the rightmost.

3. Why does this method work?

By placing a tower at the rightmost candidate among those that can cover the leftmost village, the tower’s maximum reach to the right is also maximized. There is no advantage to placing it further left (no possibility of covering more villages to the right), so repeating this choice yields the minimum number.

Algorithm

1. Preprocessing:
   • Sort all villages in ascending order of position \(X\).
   • Extract a list eligible_x of positions of “eligible villages” satisfying altitude \(P_i \ge K\).
2. Greedy Selection:
   • Let \(x_{target}\) be the position of the leftmost village not yet covered.
   • Using binary search, find the maximum position (rightmost) in eligible_x that is at most \(x_{target} + D\). Call this \(x_{tower}\).
   • If the found \(x_{tower}\) is at least \(x_{target} - D\), place a radio tower at that village.
     • The placed tower covers all villages up to \(x_{tower} + D\).
     • Update the next uncovered village to the first village whose position is greater than \(x_{tower} + D\).
   • If no suitable \(x_{tower}\) is found (no eligible village exists within the range), it is impossible to cover all villages, so output -1 and terminate.
3. Repeat until all villages are covered, then output the total number of towers placed.

Complexity

• Time Complexity: \(O(N \log N)\)
  • Sorting the villages takes \(O(N \log N)\).
  • Each step of the greedy algorithm performs a binary search (bisect_right), but since at least one village is covered per step, the overall complexity is \(O(N \log N)\).
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used to store village information.

Implementation Notes

• Using Binary Search: When searching for the optimal placement among eligible villages or finding the next village to cover, using bisect_right enables efficient processing.

• Detecting Impossible Cases:

  • When there are no eligible villages at all.
  • When for the leftmost uncovered village \(x_{target}\), all eligible villages are either only at positions less than \(x_{target} - D\) or only at positions greater than \(x_{target} + D\). In these cases, -1 must be returned immediately.

• Fast I/O: Since \(N = 2 \times 10^5\) can be large, in Python using sys.stdin.read().split() or similar methods to read all input at once can reduce execution time.

  Source Code

import sys
from bisect import bisect_right

def solve():
    # 高速な入力読み込みのために sys.stdin.read().split() を使用
    data = sys.stdin.read().split()
    if not data:
        return
    
    # 村の数 N, 設置可能な最小標高 K, 電波の届く距離 D を取得
    N = int(data[0])
    K = int(data[1])
    D = int(data[2])
    
    # 各村の位置 X と標高 P を取得
    villages = [None] * N
    it = iter(data[3:])
    for i in range(N):
        x = int(next(it))
        p = int(next(it))
        villages[i] = (x, p)
    
    # メモリ節約のため、元のデータリストを削除
    del data
    
    # 村を位置 X の昇順にソート
    villages.sort(key=lambda v: v[0])
    
    # 全ての村の位置 X のリスト
    X = [v[0] for v in villages]
    # 電波塔を設置可能な村の位置 X のリスト
    eligible_x = [v[0] for v in villages if v[1] >= K]
    
    # ソート済みの villages リストもメモリ節約のため削除
    del villages
    
    # 設置可能な村が一つもない場合
    if not eligible_x:
        print("-1")
        return

    ans = 0
    i = 0
    while i < N:
        # 現在まだカバーされていない最も左側にある村の位置
        x_target = X[i]
        
        # 強欲法（Greedy Algorithm）:
        # 左端の村 x_target をカバーできる電波塔のうち、
        # 最も右側に設置できる（＝右方向へのカバー範囲が最大になる）村を選択する。
        # その条件は、x_target - D <= tower_x <= x_target + D かつ標高が K 以上。
        
        # 条件 1: tower_x <= x_target + D を満たす最大の tower_x を二分探索で見つける
        idx = bisect_right(eligible_x, x_target + D)
        
        if idx == 0:
            # x_target + D より左側に設置可能な村が一つも存在しない場合
            print("-1")
            return
        
        tower_x = eligible_x[idx - 1]
        
        # 条件 2: 見つけた tower_x が x_target をカバーできるか確認 (tower_x >= x_target - D)
        if tower_x < x_target - D:
            # 設置可能な村の中で最も右にあるものでさえ、x_target まで届かない場合
            print("-1")
            return
        
        # 電波塔を設置
        ans += 1
        
        # この電波塔は [tower_x - D, tower_x + D] の範囲をカバーする。
        # 次にカバーすべき村は、tower_x + D より右側にある最初の村。
        i = bisect_right(X, tower_x + D)
        
    # 必要な電波塔の最小数を出力
    print(ans)

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-preview.