Codeforces #210 Div1. A. Levko and Array Recovery

昨晩えらい遅い時間に開催されたCF210に参加。
Aの時点でいつもより難易度が高く、standingsが埋まるのが遅い。

結局A,Bを解いてそこそこの順位。
CはRedcoderでも正解者が少なく難易度が高かったようだ。
A,Bで凡ミスでpretest突破に手間取ったのが痛いな。
http://codeforces.com/contest/360/problem/A

問題

整数値からなる数列Aがある。
ここで、以下のいずれかのクエリを処理した履歴がQ回分残っていた。

1. L,R,Dの3値が与えられ、A[L]～A[R]までの要素にDを加算する。
2. L,Rの2値が与えられ、A[L]～A[R]までの最大値はMだった。

上記クエリ履歴を再現できるような数列Aがあれば答えよ。

解法

Aの値を大きな値に仮置きし、クエリを逆順に処理していけばよい。
クエリのタイプ1ならDを減算し、タイプ2ならA[i]の値がM以上ならMに押さえる。

逆順処理が完了してAを決めたら、再度クエリを順に処理し、タイプ2のクエリでちゃんと最大値を再現できるか検証すればよい。

int N,M;
int A[10000],B[10000];
int T[4][10000];
void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M;
	FOR(i,N) A[i]=1<<29;
	FOR(i,M) {
		cin>>T[0][i]>>T[1][i]>>T[2][i]>>T[3][i];
		T[1][i]--;T[2][i]--;
	}
	
	for(i=M-1;i>=0;i--) {
		if(T[0][i]==1) {
			for(j=T[1][i];j<=T[2][i];j++) A[j]-=T[3][i];
		}
		else {
			for(j=T[1][i];j<=T[2][i];j++) A[j]=min(A[j],T[3][i]);
		}
	}
	
	int ng=0;
	memmove(B,A,sizeof(A));
	FOR(i,M) {
		int y=-1<<29;
		if(T[0][i]==1) for(j=T[1][i];j<=T[2][i];j++) B[j]+=T[3][i];
		else {
			for(j=T[1][i];j<=T[2][i];j++) y=max(y,B[j]);
			if(y!=T[3][i]) ng=1;
		}
	}
	if(ng) _P("NO\n");
	else {
		_P("YES\n");
		FOR(i,N) _P("%d ",A[i]);
		_P("\n");
	}
}

まとめ

Div1とはいえAの割にややこしい問題。
自分もクエリを逆順処理した後再度処理するってのに気づくまで少しかかった。