kmjp's blog

競技プログラミング参加記です

Codeforces #305 Div1 B. Mike and Feet

本番長々コードを書いたけど、落ち着いたら簡単だった。
http://codeforces.com/contest/547/problem/B

問題

N要素の整数列A[i]が与えられる。
A中の連続するL要素の最小値の最大値をf(L)とする。
各L=1~Nについて、f(L)を求めよ。

解法

stackを使いAを先頭から走査していく。
これにより各A[i]について、A[j]~A[i]≧A[i]かつA[j-1]<A[i]となるjを求められる。
この場合f(i-j+1)の候補はA[i]となる。

あとはf(L)=max(f(L),f(L+1))の要領で前記走査の結果からf(L)を更新しておくと良い。

int N;
int le[202000],ri[202000];
int lenma[202000];
int H[202000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	stack<pair<int,int> > S;
	S.push(make_pair(-1,-1));
	
	cin>>N;
	
	FOR(i,N) {
		cin>>H[i];
		while(S.top().first > H[i]) ri[S.top().second]=i-S.top().second, S.pop();
		S.push(make_pair(H[i],i));
	}
	while(S.size()>1) ri[S.top().second]=N-S.top().second, S.pop();
	
	S.pop();
	S.push(make_pair(-1,N));
	for(i=N-1;i>=0;i--) {
		while(S.top().first > H[i]) le[S.top().second]=S.top().second-i, S.pop();
		S.push(make_pair(H[i],i));
	}
	while(S.size()>1) le[S.top().second]=S.top().second+1, S.pop();
	
	FOR(i,N) lenma[le[i]+ri[i]-1]=max(lenma[le[i]+ri[i]-1], H[i]);
	
	for(i=N;i>=1;i--) lenma[i]=max(lenma[i],lenma[i+1]);
	FOR(i,N) _P("%d ",lenma[i+1]);
	_P("\n");
}

まとめ

本番はpriority_queueを使って要素の大きな順に区間を連結していった。
stackでこんなあっさり書けたのね。