Codeforces #310 Div1 B. Case of Fugitive

CFで良く見るネタ。
http://codeforces.com/contest/555/problem/B

問題

１次元の数直線上で、N個の閉区間[L[i],R[i]]がある。
これらは昇順に並んでおり、共通点を持たない。

ここで、M個の橋がありそれぞれの長さはA[i]である。
隣接する区間をこれらの橋を使ってつなぎたい。
もちろん各橋は１個ずつしか使えない。

全ての隣接区間をこれらの橋で接続できるか。
できるなら橋の割り当て方の例を示せ。

解法

i番の区間と(i+1)番の区間をつなぐ橋の長さは[L[i+1]-R[i],R[i+1]-L[i]]の範囲に含まれる橋でなければならない。

あとは区間スケジューリングの要領で橋の割り当てを行えばよい。
すなわち必要な橋の長さの範囲を最大値の順で昇順ソートし、使用可能な橋のうち短い順に選択していけばよい。

int N,M;
ll L[202020],R[202020],MA[202020],MI[202020],A[202020];
int id[202020];
set<pair<ll,int> > EV;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N>>M;
	FOR(i,N) cin>>L[i]>>R[i];
	FOR(i,M) {
		cin>>A[i];
		EV.insert({A[i],i+1000000});
	}
	
	FOR(i,N-1) {
		MI[i]=L[i+1]-R[i];
		MA[i]=R[i+1]-L[i];
		EV.insert({MI[i],i});
	}
	
	set<pair<ll,int> > S;
	
	FORR(r,EV) {
		int ev = r.second;
		if(ev<1000000) {
			S.insert({MA[ev],ev});
		}
		else if(ev<2000000) {
			ev-=1000000;
			auto s=S.begin();
			if(s==S.end()) continue;
			
			if(A[ev]>s->first) return _P("No\n");
			id[s->second]=ev+1;
			S.erase(s);
		}
	}
	
	if(S.size()) return _P("No\n");
	_P("Yes\n");
	FOR(i,N-1) _P("%d ",id[i]);
}

まとめ

これはあまりヒネリのない典型ネタっぽかった。