Codeforces #165 Div1 D. Maximum Waterfall

うーん、やはりCodeforcesの問題は実装がめんどい。
http://codeforces.com/contest/269/problem/D

問題

高さHのフィールドがあり、そこにN個のセグメントがある。
各セグメントは高さh[i](0

• 高さHのセグメントには無限の水が流れ込んでいると考えてよい。
• 水は高いセグメントから低いセグメントに流れる。
• 流せる水の量は、高いセグメントと低いセグメントの共通部分の長さと、高い方のセグメントに流れている水量の少ない方である。
• セグメントxからセグメントyに水を流そうとしても、セグメントxとyの間にx→z、z→yと流せるような別のセグメントがある場合xからyに直接水は流せない。

最大の単一水量を答えよ。

解法

高さの低い順に処理していく。
現在の高さから下を見て見えるセグメント群の左端の座標をsetで管理する。

あるセグメントxを処理する際、setのlower_boundを使いL[x]～R[x]の範囲と共通部分のある低位のセグメント群を処理していく。
set中で左端の順にa、b、cとセグメントが並んでいるとする。上記4番目の条件、すなわちx→a→bまたはx→c→bのいずれかの順で水が流せないなら、x→bで水を流すことができるので、水量の最大値を更新していく。
セグメントxを処理することで、そのセグメントの下にあるセグメント群はsetから外していけばよい。

int N,T;
ll H[100050],L[100050],R[100050],F[100050];
vector<pair<ll,int> > V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>T;
	FOR(i,N) cin>>H[i]>>L[i]>>R[i];
	H[N]=T,L[N]=(-1<<30)+1,R[N]=(1<<30)-1;
	H[N+1]=0,L[N+1]=-1<<30,R[N+1]=1<<30,F[N+1]=1LL<<31;
	N+=2;
	FOR(i,N) V.push_back(make_pair(H[i],i));
	sort(V.begin(),V.end());
	
	set<pair<ll,int> > S;
	set<pair<ll,int> >::iterator sit,cur,p,n;
	S.insert(make_pair(L[N-1],N-1));
	S.insert(make_pair(R[N-1],N-1));
	for(i=1;i<N;i++) {
		j=V[i].second;
		cur=sit=S.lower_bound(make_pair(L[j],j));
		for(cur--;cur!=S.end() && cur->first < R[j];cur++) {
			p=n=cur;
			if(p!=S.begin()) p--;
			if(n!=S.end()) n++;
			x=p->second,y=n->second,r=cur->second;
			if(H[x]>H[r] && min(R[j],R[x])-max(L[j],L[x])>0 && min(R[x],R[r])-max(L[x],L[r])>0) continue;
			if(H[y]>H[r] && min(R[j],R[y])-max(L[j],L[y])>0 && min(R[y],R[r])-max(L[y],L[r])>0) continue;
			F[j]=max(F[j],min(F[r],min(R[j],R[r])-max(L[j],L[r])));
		}
		p=cur;
		p--;
		x=p->second;
		S.erase(sit,cur);
		if(cur->first>R[j]) S.insert(make_pair(R[j],x));
		S.insert(make_pair(L[j],j));
	}
	cout<<F[N-2]<<endl;
}

まとめ

理屈はわかるけど、だいぶ実装がめんどい。