AtCoder Beginner Contest 128 E - Roadwork stl+思维

题目链接
大意：给你一系列的障碍物的信息（出现位置和时间），然后给你一系列的人的出发时间（从零坐标开始），问你每个人最多能走多远。
思路：我们可以换个方式思考，不考虑人，考虑每个障碍物可以挡住哪些人，先将障碍物按坐标从小到大排序，然后将所有的人存进set中，遍历所有的障碍物，每次二分查找位置 $[l_i,r_i)$[li​,ri​)，左闭右开的障碍物区间，（事先将障碍物的存在时间减去坐标，即等价于0坐标出障碍物的时间），然后更新答案即可了，然后删除更新过的人，每个人只会被删一次。
细节见代码。

#include<bits/stdc++.h>

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 4e5 +11;
int n,m,cnt,d,b[N],ans[N];;
struct uzi{int s,t,x,i;}p[N];
struct faker{int x,i; bool operator <(const faker & t)const{return x<t.x;} }a[N];
int cmp(uzi a,uzi b){return a.x<b.x;}
map<int,int>pos;
bool operator < ( pair<int,int>A,pair<int,int>B ){return A.fi<B.fi;}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	memset(ans,-1,sizeof ans);
	for(int i=1;i<=n;i++){
		cin>>p[i].s>>p[i].t>>p[i].x;
		p[i].s-=p[i].x;p[i].t-=p[i].x;p[i].i=i;
		p[i].s=max(p[i].s,0);
		p[i].t=max(p[i].t,0);
	}
	sort(p+1,p+1+n,cmp);
	for(int i=1;i<=m;i++)cin>>a[i].x,a[i].i=i,pos[a[i].x]=i;
	set<int>s;
	for(int i=1;i<=m;i++)s.insert(a[i].x);
	for(int i=1;i<=n;i++){//当前这个区间选择一些可以满足的数[p[i].s,p[i].t),左闭右开
		auto l=s.lower_bound(p[i].s);
		auto k=s.lower_bound(p[i].t);
		vector<int>q;
		for(auto j=l;j!=k;j++){
			ans[pos[*j]]=p[i].x;
			q.pb(*j);
		}
		for(auto j:q)s.erase(j);
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';cout<<endl;
	return 0;
}
// 找最小的位置，使得该位置的时间包含d
// 可以找每个障碍点控制的范围（指人
// 4 6
// 1 3 2
// 7 13 10
// 18 20 13
// 3 4 2
// 0
// 1
// 2
// 3
// 5
// 8


// 2
// 2
// 10
// -1
// 13
// -1