test
JOI2014春day1-bus
bus[i] バス(出発地点a,到着地点b,出発時間x,到着時間y)
バスを着くのが遅い(yが大きい)順にソート
t[i]=バスiに乗った時に目的地につける最も早い時間
busstop[i]=バス停iから出るバス達のP(x(出発時間),バス番号)
tmp[i]=バス停iをどこまで見たか
着くのが遅い順にtを更新していく
t[i]=min(そのバスのbから乗れるバス達のt) (着くのが遅い順なのでこれらは全て更新済みになる)
これらをいちいち見てると死ぬので、tmp[i]で遅い方からどこまで見たか保存しておく(後の参照ほど乗れるバスが多いのでtmp[i]とまだ見てない奴だけを見れば良い)これでここにかかる時間がO(N)になる
あとはbus0(バス停0から出るバス)を適当になんかすれば良い
#include <iostream> #include <cstdio> #include <vector> #include <algorithm> using namespace std; #define rep(i,n) for(int i=0;i<(n);++i) #define rep1(i,n) for(int i=1;i<=(n);++i) #define ALL(c) (c).begin(),(c).end() typedef pair<int,int> P; struct bus{int a,b,x,y;}; bool ylate(const bus& l,const bus& r){ if(l.y!=r.y) return l.y>r.y; if(l.x!=r.x) return l.x>r.x; if(l.b!=r.b) return l.b>r.b; return l.a>r.a; } vector<bus> vc; P tmp[100000]; vector<P> busstop[100000],bus0; int t[300000],inf=1e+9; int main(){ int n,m,q; scanf("%d%d",&n,&m); rep(i,m) t[i]=inf; rep(i,n) tmp[i]=P(inf,inf); //? rep(i,m){ int a,b,x,y; scanf("%d%d%d%d",&a,&b,&x,&y); a--;b--; bus abus={a,b,x,y}; vc.push_back(abus); } sort(ALL(vc),ylate);//y遅い順にソート rep(i,m) busstop[vc[i].a].push_back(P(vc[i].x,i)); rep(i,n) sort(ALL(busstop[i])); rep(i,m){ int s=vc[i].b,li=vc[i].y; if(s==n-1){ t[i]=li; continue; } int it=lower_bound(ALL(busstop[s]),P(li,-1))-busstop[s].begin(); int ret=tmp[s].second; for(int j=it;j<busstop[s].size() && busstop[s][j].first<tmp[s].first;j++){ ret=min(ret,t[busstop[s][j].second]); } t[i]=ret; } rep(i,m){ if(vc[i].a!=0 || t[i]==inf) continue; bus0.push_back(P(t[i],vc[i].x)); } scanf("%d",&q); if(bus0.empty()){ rep(i,q) printf("-1\n"); return 0; } sort(ALL(bus0)); rep(i,bus0.size()-1) bus0[i+1].second=max(bus0[i+1].second,bus0[i].second); rep(i,q){ int l; scanf("%d",&l); int ans=upper_bound(ALL(bus0),P(l,inf))-bus0.begin()-1; if(ans==-1) printf("-1\n"); else printf("%d\n",bus0[ans].second); } return 0; }
ansの定義らへんでコーナーケース気付かずにバグらせて死んでいた