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

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の定義らへんでコーナーケース気付かずにバグらせて死んでいた