Codeforces #207 Div1. A. Knight Tournament

CF#207に参加。
本番の感触はB

問題

1～N番の人が試合をしていく。
各試合では、L[i]～R[i]番の間の残った人が試合をし、X[i]番の人が勝ち残り、それ以外の人はX[i]番に負けて試合脱落となる。
各人が何番の人に負けたかを列挙せよ。

解法

律儀に試合をシミュレートするとO(N^2)かかってしまい、N<=10^5の環境ではTLEする。

1つはSegTreeを使う方法で、L[i]～(X[i]-1)番および(X[i]+1)～R[i])番がX[i]番に負けた、という記録をどんどん保存していく。

もう一つは自分が使った手法で、各人が次に残っている番号を覚えていく。
各試合でL[i]～R[i]番の人を処理する際、(L[i]-1)番の次はX[i]番、X[i]番の次は(R[i]+1)番となるようにする。
vectorの配列をeraseする必要がないので高速に処理できる。

int N,M;
vector<int> L;
int C[500001];

void solve() {
	int f,i,j,k,l,r, x,y;
	
	cin>>N>>M;
	FOR(i,N) L.push_back(i+1);
	FOR(i,N) C[i]=0;
	
	FOR(i,M) {
		cin>>l>>r>>x;
		l--;r--;x--;
		
		for(j=l;j<=r;) {
			k=L[j];
			if(C[j]==0) C[j]=x+1;
			if(j<x) L[j]=x;
			else L[j]=L[r];
			j=k;
		}
		C[x]=0;
	}
	
	FOR(i,N) _P("%d ",C[i]);
	_P("\n");
}

まとめ

まさかAでSegTreeが出てくるとは…。