読者です 読者をやめる 読者になる 読者になる

kmjp's blog

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

Croc Champ 2013 - Round 1 : E. Copying Data

さて最終問題。これも本番に解けて良かった。
http://codeforces.com/contest/292/problem/E

問題

2つの整数値配列A,Bが与えられる。
そこに与えられる以下のクエリを処理せよ。

  1. X,Y,Lが与えられるので、A[X]~A[X+L-1]をB[Y]~B[Y+L-1]にコピー
  2. Xが与えられるので、B[X]を返す

解法

BITを使って、Bの各要素がどのクエリの時の値を保持するか記憶すればよい。

手元のBITライブラリが各要素の累積値を持つものだったので、クエリの値を持つよう書き直した。

int N,M;
int A[100001];
int B[100001];
const int BITL=19;
typedef pair<int,int> rec ;
rec P[1<<BITL];

void update(int cur,int L,int R,rec p) {
	int bl=0;
	if(L==R) return;
	while(cur>=1<<(bl+1)) bl++;
	int tl=(cur-(1<<bl))<<(BITL-bl-1);
	int tr=(cur-(1<<bl)+1)<<(BITL-bl-1);
	int tm=(tl+tr)/2;
	
	if(tl==L && tr==R) {
		P[cur]=p;
	}
	else {
		if(P[cur].first!=-2) {
			update((1<<(bl+1))+(tl>>(BITL-bl-2)),tl,tm,P[cur]);
			update((1<<(bl+1))+(tm>>(BITL-bl-2)),tm,tr,P[cur]);
		}
		P[cur]=make_pair(-2,0);
		if(L<tm) update((1<<(bl+1))+(tl>>(BITL-bl-2)),L,min(tm,R),p);
		if(R>=tm) update((1<<(bl+1))+(tm>>(BITL-bl-2)),max(L,tm),R,p);
	}
}
void update(int L,int R,rec p) { update(1,L,R,p);}

pair<int,int> val(int entry) {
	int i;
	rec p;
	FOR(i,BITL) {
		p=P[(1<<i)+(entry>>(BITL-i-1))];
		if(p.first!=-2) return p;
	}
	return make_pair(-1,0);
}

void solve() {
	int f,r,i,j,k,l,x,y;
	int ma=0;
	
	GET2(&N,&M);
	FOR(i,N) A[i]=GETi();
	FOR(i,N) B[i]=GETi();
	FOR(i,1<<BITL) P[i]=make_pair(-2,0);
	FOR(i,N) update(i,i+1,make_pair(-1,0));
	
	FOR(i,M) {
		j=GETi();
		if(j==1) {
			x=GETi()-1;
			y=GETi()-1;
			l=GETi();
			update(y,y+l,make_pair(x,y));
			/*
			FOR(j,N) {
				rec p = val(j);
				_P("(%d,%d) ",p.first,p.second);
			}
			_P("\n");
			*/
		}
		else {
			k=GETi()-1;
			rec p = val(k);
			//_P("%d %d %d\n",k,p.first,p.second);
			
			if(p.first==-1) _P("%d\n",B[k]);
			else _P("%d\n",A[p.first+(k-p.second)]);
		}
	}
	
	return;
}

まとめ

これ、クエリ情報としてXとYのペアを覚えておくようにしたけど、考えたらクエリの番号だけ覚え解けばペアの処理をしなくてよくて楽だったな。

今回は問題読み落としやらデータ構造選択のポカミスなど、スコア・時間の小さなロスを積み重ねてしまってもったいなかった。
時間切れとはいえ全部自力で解けたし、Round1抜けたしまぁ上出来だけどね。

広告を非表示にする