Codeforces #335 Div1 D. Board Game

本番こっち解けば良かった…。
http://codeforces.com/contest/605/problem/D

問題

プレイヤーのスキルは2つのパラメータ(x,y)で表される。
初期状態ではスキルは(0,0)である。

ここでN種類の魔法を唱えたい。
i番目の魔法はパラメータA[i],B[i],C[i],D[i]であらわされる。
x≧A[i]かつy≧B[i]ならばこの魔法を唱えることができる。
また魔法を唱えるとプレイヤーのパラメータは(C[i],D[i])になる。

N番目の魔法をとなえるまでに必要な最小魔法詠唱数及び唱える順番の例を求めよ。

解法

色々解法がありそうだが、自分は座標圧縮＋平方分割で解いた。
まずx軸側で登場する数値A[i],C[i]を座標圧縮しよう。
するとx軸で登場する値は2*N個程度になる。

後はx座標をD=√(2*N)個程度の領域に分割し、個々の領域についてsetで未詠唱の魔法をy座標順で管理しよう。
また、それとは別にx座標毎にもsetで未詠唱の魔法をy座標順で管理しよう。

あとはダイクストラの要領で、未詠唱かつ詠唱可能な魔法を探索していく。
プレイヤーのパラメータが(Px,Py)なら、k*D＜Pxであるようなkに対し、個々の領域でsetを参照してy座標がPy以下の魔法を唱えていく。
またk*D＜x≦Pxの範囲のxについては、x座標毎のsetを同様に探索すればよい。

int N;
int A[101010],B[101010],C[101010],D[101010];
vector<int> VA;
set<pair<int,int> > ST[500];
set<pair<int,int> > S[200000];
int from[101010],cost[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	VA.push_back(0);
	VA.push_back(1<<30);
	queue<int> Q;
	cin>>N;
	FOR(i,N) {
		cin>>A[i]>>B[i]>>C[i]>>D[i];
		VA.push_back(A[i]);
		VA.push_back(C[i]);
	}
	sort(ALL(VA));
	VA.erase(unique(ALL(VA)),VA.end());
	FOR(i,N) {
		A[i]=lower_bound(ALL(VA),A[i])-VA.begin();
		C[i]=lower_bound(ALL(VA),C[i])-VA.begin();
		if(A[i]||B[i]) {
			ST[A[i]/500].insert({B[i],i});
			S[A[i]].insert({B[i],i});
			cost[i]=101010;
		}
		else {
			cost[i]=0;
			from[i]=-1;
			Q.push(i);
		}
	}
	
	while(Q.size()) {
		int cur=Q.front();
		Q.pop();
		
		x=C[cur];
		y=D[cur];
		FOR(i,x/500) {
			while(ST[i].size() && ST[i].begin()->first<=y) {
				int tar=ST[i].begin()->second;
				cost[tar] = cost[cur]+1;
				from[tar] = cur;
				Q.push(tar);
				S[A[tar]].erase({B[tar],tar});
				ST[i].erase(ST[i].begin());
			}
		}
		for(i=x/500*500;i<=x;i++) {
			while(S[i].size() && S[i].begin()->first<=y) {
				int tar=S[i].begin()->second;
				cost[tar] = cost[cur]+1;
				from[tar] = cur;
				Q.push(tar);
				ST[A[tar]/500].erase({B[tar],tar});
				S[i].erase(S[i].begin());
			}
		}
	}
	
	
	if(cost[N-1]>N) return _P("-1\n");
	vector<int> R;
	x=N-1;
	while(x>=0) {
		R.push_back(x);
		x=from[x];
	}
	_P("%d\n",R.size());
	FOR(i,R.size()) _P("%d ",R[R.size()-1-i]+1);
	_P("\n");
	
	
}

まとめ

最近setで殴る手段取りすぎ…。