Codeforces #344 Div2. C. Report

A～Dはさほど難しくないが、Eは少し難しめ。
http://codeforces.com/contest/631/problem/C

問題

N要素の数列Aが与えられる。
このAに対し、以下の処理をM回行う。

• 先頭R[i]個の要素だけを昇順または降順に並べ替える。

最終的にAはどうなるか答えよ。

解法

各クエリをR[i]降順にソートしよう。
R[i]の最大値をpとする。
まずAのうち(0-originで)A[p]以降の要素はどのクエリでも操作されないので、それらは何もいじらない。

以後、A[i]をA[p-1],A[p-2]...と後ろから順に決めていこう。

A[i]がどうなるかは、Aのうち未確定な(i+1)要素に対し、iより大きな並べ替え範囲を持つ最後のクエリが昇順降順どちらかによって決まる。
最後が昇順なら未確定のうち最大値、降順なら最小値を取ればよい。

int N,M;
int A[202020];
int B[202020];
int T[202020];
int R[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i], B[i]=A[i];
	int ma=0;
	FOR(i,M) {
		cin>>x>>y;
		ma=max(ma,y);
		T[y]=i+1;
		R[y]=x;
	}
	sort(A,A+ma);
	x=0;
	y=ma-1;
	j=0;
	int t=0;
	for(i=N-1;i>=0;i--) {
		if(T[i+1]>t) j=R[i+1], t=T[i+1];
		if(t>0) {
			if(j==2) B[i]=A[x++];
			else B[i]=A[y--];
		}
	}
	FOR(i,N) _P("%d%s",B[i],(i==N-1)?"\n":" ");
}

まとめ

本番意外とすんなり思いつけた。