Codeforces #283 Div1 C. Distributing Parts

これ系の問題Codeforcesでしばしば見かけるね。
http://codeforces.com/contest/497/problem/C

問題

M人でNパートからなる歌を歌いたい。
各パートは、歌うのに必要な声の高さの範囲はC[i]～D[i]であり、１人が担当する。

各人は、A[i]～B[i]の声の高さに含まれるパートのみ歌うことができる。
また、各人はK[i]パートまでしか歌うことができない。

この曲を歌いきることができるか。
出来るなら、各パートを誰が歌えば良いか例を答えよ。

解法

尺取法の要領で行う。
声の高さの低い順に、各パート及び各人をイベントとして処理していく。

• 今処理している声の高さをxとする。
  • 声C[i]==xの人を、「歌うことができる人の集合」に加え、その際最高値のD[i]を登録する。
  • 高さA[j]==xのパートがあったとする。「歌うことができる人の集合」のうち、D[i]がB[j]以上最小の人の番号を求め、その人をこのパートに割り当てる。
    • この際、この人が歌えるパート数に達成した場合、この人を「歌うことができる人の集合」から外す。
  • 声D[i]==xの人を、「歌うことができる人の集合」から外す。

int N,A[102000],B[102000];
int M,C[102000],D[102000],K[102000];
set<pair<int,int> > S,ev;
int ret[102000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i]>>B[i], ev.insert(make_pair(A[i],i+100000));
	cin>>M;
	FOR(i,M) cin>>C[i]>>D[i]>>K[i], ev.insert(make_pair(C[i],i)), ev.insert(make_pair(D[i],i+200000));
	
	ITR(it,ev) {
		if(it->second<100000) {
			S.insert(make_pair(D[it->second],it->second));
		}
		else if(it->second<200000) {
			int cur=it->second-100000;
			
			set<pair<int,int> >::iterator sit=S.lower_bound(make_pair(B[cur],0));
			if(sit==S.end()) return _P("NO\n");
			ret[cur]=sit->second+1;
			if(--K[sit->second]==0) S.erase(sit);
		}
		else {
			S.erase(make_pair(D[it->second-200000],it->second-200000));
		}
	}
	
	_P("YES\n");
	FOR(i,N) _P("%d ",ret[i]);
	_P("\n");
}

まとめ

C問題だけど、1250ptということでいつもよりちょっと簡単。