kmjp's blog

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

AtCoder ABC #254 : G - Elevators

Exの方が楽だった回。
https://atcoder.jp/contests/abc254/tasks/abc254_g

問題

N個の建物があり、計M個のエレベーターが動いている。
各エレベーターは、1つの建物であるフロアの区間を動いており、時間1で1つフロアを移動できる。
また、異なる建物同士の同じフロアも、時間1で移動できる。

以下のクエリに答えよ。

  • 建物XのフロアYから、建物ZのフロアWに移動する最小時間

解法

Y>Wの場合、スタートとゴールを逆にして、Y≦Wにしておこう。
この問題設定では、あえてエレベーターを下るメリットはないので、エレベーターは上りのみ使うことになる。
とすると縦方向の移動時間は確定するので、あとは建物間の移動回数を最小化する問題となる。

まず、同一の建物で区間が重複するエレベーターは、マージして1つにしておこう。
また、最初建物X内で移動できる範囲でYをできるだけ上に移動しておき、同様に建物Z内で移動できる範囲でWをできるだけ下に下げておこう。
この時点でY≧Wなら0回または1回の建物間移動で済む。

そうでない場合、1回建物移動をするとどこまでの高さに行けるかを求め、かつダブリングした値を計算しておこう。
そしてYからWに移動する最小回数を求めればよい。

int N,M,Q;
vector<pair<int,int>> E[202020];
int X[202020],Y[202020],Z[202020],W[202020];
int R[22][806060];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>Q;
	vector<int> Vs;
	Vs.push_back(1);
	Vs.push_back(100000001);
	
	FOR(i,M) {
		cin>>x>>y>>k;
		E[x-1].push_back({y,k});
		Vs.push_back(y);
		Vs.push_back(k);
	}
	FOR(i,Q) {
		cin>>X[i]>>Y[i]>>Z[i]>>W[i];
		X[i]--;
		Z[i]--;
		if(Y[i]>W[i]) swap(Y[i],W[i]),swap(X[i],Z[i]);
		Vs.push_back(Y[i]);
		Vs.push_back(W[i]);
	}
	
	
	sort(ALL(Vs));
	Vs.erase(unique(ALL(Vs)),Vs.end());
	FOR(i,N) {
		sort(ALL(E[i]));
		vector<pair<int,int>> V;
		FORR2(a,b,E[i]) {
			a=lower_bound(ALL(Vs),a)-Vs.begin();
			b=lower_bound(ALL(Vs),b)-Vs.begin();
			R[0][a]=max(R[0][a],b);
			if(V.empty() || a>V.back().second) {
				V.push_back({a,b});
			}
			else {
				V.back().second=max(V.back().second,b);
			}
		}
		FORR2(a,b,V) R[0][a]=max(R[0][a],b);
		E[i]=V;
	}
	FOR(i,Vs.size()) if(i) R[0][i]=max({R[0][i],R[0][i-1],i});
	FOR(i,20) {
		FOR(j,Vs.size()) R[i+1][j]=R[i][R[i][j]];
	}
	
	FOR(i,Q) {
		ll sum=W[i]-Y[i];
		x=lower_bound(ALL(Vs),Y[i])-Vs.begin();
		y=lower_bound(ALL(Vs),W[i])-Vs.begin();
		j=lower_bound(ALL(E[X[i]]),make_pair(x+1,0))-E[X[i]].begin();
		if(j&&E[X[i]][j-1].first<=x) x=max(x,E[X[i]][j-1].second);
		j=lower_bound(ALL(E[Z[i]]),make_pair(y+1,0))-E[Z[i]].begin();
		if(j&&E[Z[i]][j-1].second>=y) y=min(y,E[Z[i]][j-1].first);
		
		if(x>=y) {
			cout<<sum+(X[i]!=Z[i])<<endl;
			continue;
		}
		if(R[20][x]<y) {
			cout<<-1<<endl;
			continue;
		}
		for(j=19;j>=0;j--) if(R[j][x]<y) {
			sum+=(1<<j);
			x=R[j][x];
		}
		sum+=2;
		cout<<sum<<endl;
	}
	

}

まとめ

しょうもないバグを埋め込んでしまい、解決に手間取った。