UTPC2013 G 夏休みの掃除当番

問題

日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_07）

夏休みがM日あって、N人の掃除当番を使って、
「連続して掃除がされない日数の最大値」をなるべく小さくしたい。

i番目の人はa[i]日目〜b[i]日目のうち一日だけ掃除ができる。

N人のうちK人以下を自由に選んで、その人はa[i]〜b[i]日目を全部掃除させることができる。
連続して掃除がされない日数の最大値の最小値を求めよ。

制約条件

N≦10^5
M≦10^9
0≦K≦N
夏休みのちょうど前日と、最後の翌日は掃除されていると考える。

方針

間隔をあけられる最大値を二分探索。

基本的に次のことを繰り返す。
今カバーしている区間の右端以内にa[i]が入る人を全員持ってくる。
その中で、最もb[i]が早い人を選んで、その人に区間のギリギリで掃除させる。

掃除できる人がいなくなってしまったら、
今まで使った中で、b[i]が最も良かった人を毎日掃除させるように変更する。

この貪欲を、b[i]が早い人を選ぶところでpriority queueを使って速くすればいい。

何でこれでいいかというと、
まずb[i]が早い人Pより先にb[i]が遅い人Qを使ってもよくならないことを言う。
Qが掃除する日を先延ばしに出来る場合、
Pにギリギリのところで掃除させたら区間が延びるので、その後でQに掃除させたほうが明らかに得だから。

次に毎日掃除する人はできるだけギリギリに決めたほうがいいことについては、
前のほうで毎日掃除することにしても、今使った人の一番でかいb[i]までしか区間は伸ばせない。
ならば一番でかいb[i]の人を毎日掃除させることにしても同じ。

ソースコード

int n, m, choice;
vector<pi> students;
 
inline bool ok_2(int mid){
	int cur_choice = choice;
	int covered = 0, used = 0;
	int rightmost = 0;
	priority_queue<int, vi, greater<int> > candidate;
	
	while(covered + mid <= m){
		
		while(used < n && students[used].first <= covered + mid){
			
			candidate.push(students[used].second);
			used++;
		}
		
		if(candidate.empty()){
			if(used == 0)        return 0;
			if(--cur_choice < 0) return 0;
			covered = max(covered, rightmost);
		}
		if(candidate.size()){
			covered = max(covered, min(covered + mid, candidate.top()));
			rightmost = max(rightmost, candidate.top());
			
			candidate.pop();
		}
		if(covered + mid > m) return 1;
	}
	return 1;
}
 
int main(){
	cin >> n >> m >> choice;
	rep(i, n){
		int a, b;
		cin >> a >> b;
		students.pb(mp(a, b));
	}
	sort(all(students));
	
	int lo = 0, hi = m + 100, mid;
	while(lo + 1 < hi){
		mid = (lo + hi) / 2;
		if(ok_2(mid)) hi = mid;
		else lo = mid;
	}
	cout << hi << endl;
	
	return 0;
}