286D - Tourists - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define fo(i,n) for(int i(0);i^n;++i)
#define N 200010
int Q,m,n,q,x[N],y[N],t[N],f[N],v[N],p[N],o[N];
bool cmp(const int i,const int j){return t[i]<t[j];}
int get(int x){return f[x]==x?x:f[x]=get(f[x]);}
int main(){
    ios::sync_with_stdio(false);
	cin>>Q>>m;
	fo(i,m)cin>>x[i]>>y[i]>>t[i],v[n++]=x[i],v[n++]=y[i],p[i]=i;
	sort(v,v+n),n=unique(v,v+n)-v,sort(p,p+m,cmp);
	fo(i,n+1)f[i]=i,o[i]=-1;
	fo(k,m){
		int i=p[k],l=lower_bound(v,v+n,x[i])-v,r=lower_bound(v,v+n,y[i])-v;
		for(int j=get(l);j<r;j=get(j))o[j]=t[i],f[j]=j+1;
	}
	m=0;if(*o>=0)t[m++]=*o-*v;
	fo(i,n-1)if(o[i]!=o[i+1]){
		if(o[i]>=0)t[m++]=o[i]-v[i+1];
		if(o[i+1]>=0)t[m++]=o[i+1]-v[i+1];
	}
	fo(i,m)p[i]=i;
	sort(p,p+m,cmp);
	int j=0,k=0,s=0,T=0;
	fo(i,Q){
		for(cin>>q;j<m&&t[p[j]]<=q;++j)s+=k*(T-t[p[j]]),T=t[p[j]],k+=p[j]&1?-1:1;
		s+=k*(T-q),T=q,cout<<s<<endl;
	}
	return 0;
}