Codeforces #507 Div1 A. Timetable

出来がひどすぎて過去最悪のレート減を達成した。
http://codeforces.com/contest/1039/problem/A

問題

N要素の昇順列A[i]と正整数T、および整数列X[i]が与えられる。
N人の人が参加したレースで、i番目の人は時刻A[i]にスタートした。
ゴールまでには最短Tかかるが、それ以上掛けても構わない。
また、途中追い越しが発生し、ゴール順が入れ替わってもよい。

ゴール時刻を昇順に置いた数列B[i]を考える。
i番の人は最悪でも順位がX[i]となる、というようなB[i]の例を構築せよ。

解法

1-indexでX[i]＜iとなる場合解なし。よって以下X[i]≧iとする。
条件を満たすには、スタート時刻がi+1、i+2、...、X[i]番の人がi、i+1、...、X[i]-1番にゴールし、かつスタートがX[i]+1番目の人がX[i]番にゴールできない状況を作ればよい。
よってB[i]≧A[i+1]+T、B[i+1]≧A[i+2]+T、...、B[X[i]-1]≧A[X[i]-1]]+TかつB[X[i]]＜A[X[i+1]]+Tであればよい。
Bは昇順でなければいけないので、条件に反しないよう可能な限り小さい値を順に割り当てていこう。

X[i]の値によっては上記「≧」を毎回判定するとTLEするので、累積和の要領で各項目の判定要否を判断している。

int N;
ll T;
ll A[202020];
int X[202020];
ll L[202020],R[202020],C[202020];
int S[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>T;
	FOR(i,N) cin>>A[i];
	A[N]=2*1000000000000000000LL;
	
	FOR(i,N) {
		cin>>X[i];
		if(X[i]<i+1) {
			cout<<"No"<<endl;
			return;
		}
		if(i&&X[i]<X[i-1]) {
			cout<<"No"<<endl;
			return;
		}
		int D=X[i]-(i+1);
		if(i) S[i]+=S[i-1];
		S[i]++;
		S[i+D]--;
		if(X[i]!=N) R[i+D]=A[i+D+1]+T-1;
		
		if(S[i]) {
			L[i]=max(A[i+1]+T,L[i-1]+1);
		}
		else {
			L[i]=max(A[i]+T,L[i-1]+1);
		}
		if(R[i] && L[i]>R[i]) return _P("No\n");
	}
	
	
	cout<<"Yes"<<endl;
	FOR(i,N) cout<<L[i]<<" ";
	cout<<endl;
	
}

まとめ

この時点でグダってひどい目に。