以下の貪欲法が成り立ちます。

• 全ての村が電波を受信できるまで以下を繰り返す。
  • 電波が受信できていない村のうち最も座標が小さいものの座標を \(x\) とする。
  • 電波塔を設置できる座標 \(y\) にある村であって、 \(y-D \le x \le y+D\) のものが存在すれば、座標 \(x\) にある村に電波を届けることができる。
  • 座標 \(x\) にある村は電波が受信できていない村のうち最も座標が小さいものなので、 \(y\) としてありえるものが複数ある場合は最も大きいものを採用して損しない。
    • 直感的には、座標 \(x\) にある村をギリギリ覆えるまで電波塔を座標の大きい村に置くことにすることで、電波塔が覆っている部分をより座標が大きい部分まで広げることができる。

愚直に行うと実行時間制限に間に合いませんが、値をソートして upper_bound などを用いて適切に検索する・座標の小さい村から順に調べるなどで実行時間制限に間に合わせることができます。

実装例の時間計算量は \(O(N \log N)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

void fail(){
  cout << "-1\n";
  exit(0);
}

int main(){
  int N,K,D;
  cin >> N >> K >> D;
  vector<int> a,b;
  for(int i=0;i<N;i++){
    int X,P;
    cin >> X >> P;
    a.push_back(X);
    if(P>=K){
      b.push_back(X);
    }
  }
  if(b.empty()){ fail(); }
  sort(a.begin(),a.end());
  sort(b.begin(),b.end());

  int res=0;
  int cover=-1;
  for(int i=0;i<N;i++){
    if(a[i]<=cover){continue;}
    auto it=upper_bound(b.begin(),b.end(),a[i]+D);
    if(it==b.begin()){ fail(); }
    it--;
    if((*it)-D<=a[i] && a[i]<=(*it)+D){
      res++;
      cover=(*it)+D;
    }
    else{ fail(); }
  }
  cout << res << "\n";
  return 0;
}