题意

题意简述
有 $N$ 个公交站，$M$ 辆公交车，每辆车从 $A_i$ 在 $X_i$ 出发，$Y_i$ 到达 $B_i$。每天 $j$ 要求在 $L_j$ 时刻前到达站点 $N$。

求每天从站点一出发的最晚时间，若无法到达输出负一。

解法

将上面的公交车到达与出发时间，视作有向图中，每条边（公交车）有生效时间范围（发车时间 $x$，到站时间 $y$）。

我们需要为每个查询 $L$，找到从节点一到节点 $N$ 的一条路径，使得路径上所有边的到站时间都不超过 $L$，并且最大化整条路径中最小的发车时间（即从节点一出发的最晚时间）。

可以发现公交线路是有向的，且每条车只运行一次，考虑逆向时间处理或按到达时间排序并动态更新。

按到达时间升序处理公交车，维护每个站点能到达的最晚出发时间，这样保证时间具有单调性，便于后面二分处理。

如果在起点，那么最晚出发时间就是这辆车的发车时间。

否则，在起点的记录中二分查找到达时间小于等于当前车发车时间的最新记录，得到对应的最晚出发时间。

如果这个最晚出发时间比终点当前记录的最晚出发时间更优（更大），就添加新记录到终点的答案和位置中。

预处理完每辆公交车，在后续查询的时候就可以在终点站的记录中二分查找到达时间小于等于查询时间 $L_j$ 的最新记录，输出对应的最晚出发时间即可。

那么代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back 
#define F(i,a,b) for(int i=(a);i<=(b);i++)
const int N=3e5+10;
int n,m,q;
struct node{
	int a,b,x,y;
}c[N];
vector<int>ans[N],pos[N];
bool cmp(const node&x,const node&y){return x.y<y.y;}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	F(i,1,m)cin>>c[i].a>>c[i].b>>c[i].x>>c[i].y;
	sort(c+1,c+m+1,cmp);
	F(i,1,n)ans[i].pb(-1),pos[i].pb(0);
	F(i,1,m){
		int a=c[i].a,b=c[i].b,x=c[i].x,y=c[i].y,maxn=0;
		if(a==1)maxn=x;
		else {
			int lst=upper_bound(begin(pos[a]),end(pos[a]),x)-begin(pos[a])-1;
			maxn=ans[a][lst];
		}
		if(maxn>ans[b][pos[b].size()-1])ans[b].pb(maxn),pos[b].pb(y);
	}
	cin>>q;
	for(int x;q--;){
		cin>>x;
		int lst=upper_bound(begin(pos[n]),end(pos[n]),x)-begin(pos[n])-1;
		cout<<ans[n][lst]<<"\n";
	}
	return 0;
}