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; } }
まとめ
しょうもないバグを埋め込んでしまい、解決に手間取った。