求调。提交记录

#include <bits/stdc++.h>
#define int long long
using namespace std;
int dis[1000005],lsh[1000005],lson[1000005],rson[1000005];
struct abd{
	int h,l,r,lshl,lshr;
}o[1000005];
namespace sgt{
	struct abc{
		int l,r,lazy,ans;
	}t[1000005];
	void build(int x,int l,int r){
		t[x].l=l;
		t[x].r=r;
		if(l==r)return;
		int mid=(l+r)/2;
		build(2*x,l,mid);
		build(2*x+1,mid+1,r);
	}
	void pushdown(int x){
		if(t[x].lazy){
			t[2*x].lazy=t[x].lazy;
			t[2*x+1].lazy=t[x].lazy;
			t[2*x].ans=t[x].lazy;
			t[2*x+1].ans=t[x].lazy;
			t[x].lazy=0;
		}
	}
	void update(int x,int l,int r,int q){
		if(t[x].r<l||r<t[x].l)return;
		if(l<=t[x].l&&t[x].r<=r){
			t[x].lazy=q;
			t[x].ans=q;
			return;
		}
		pushdown(x);
		update(2*x,l,r,q);
		update(2*x+1,l,r,q);
	}
	int query(int x,int loc){
		if(t[x].l>loc||t[x].r<loc)return 0;
		if(t[x].l==t[x].r)return t[x].ans;
		pushdown(x);
		return query(2*x,loc)+query(2*x+1,loc);
	}
}
bool cmp(abd b,abd c){return b.h<c.h;}
vector<pair<int,int>>G[1000005];
queue<pair<int,int>>q;
priority_queue<pair<int,int>>pq;
bitset<1000005>vis;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,h;
	cin>>n>>h;
	int x,y;
	cin>>x>>y;
	int len=0;
	for(int i=1;i<=n;++i)cin>>o[i].h>>o[i].l>>o[i].r,lsh[++len]=o[i].l,lsh[++len]=o[i].r;
	sort(lsh+1,lsh+len+1);
	len=unique(lsh+1,lsh+len+1)-lsh-1;
	for(int i=1;i<=n;++i)o[i].lshl=lower_bound(lsh+1,lsh+len+1,o[i].l)-lsh;
	for(int i=1;i<=n;++i)o[i].lshr=lower_bound(lsh+1,lsh+len+1,o[i].r)-lsh;
	sort(o+1,o+n+1,cmp);
	sgt::build(1,1,len);
	for(int i=1;i<=n;++i){
		lson[i]=sgt::query(1,o[i].lshl);
		rson[i]=sgt::query(1,o[i].lshr);
		sgt::update(1,o[i].lshl,o[i].lshr,i);
	}
	q.push({n,x});
	while(!q.empty()){
		auto x=q.front();
		q.pop();
		if(x.first==0)continue;
		if(o[lson[x.first]].h-o[x.first].h<=h){
			G[x.first].push_back({lson[x.first],x.second-o[x.first].l+o[x.first].h-o[lson[x.first]].h});
			q.push({lson[x.first],o[x.first].l});
		}
		if(o[rson[x.first]].h-o[x.first].h<=h){
			G[x.first].push_back({rson[x.first],o[x.first].r-x.second+o[x.first].h-o[rson[x.first]].h});
			q.push({rson[x.first],o[x.first].r});
		}
	}
	memset(dis,0x3f,sizeof dis);
	dis[n]=0;
	pq.push({0,n});
	while(!pq.empty()){
		int x=pq.top().second,ans=pq.top().first;
		pq.pop();
		if(vis[x])continue;
		vis[x]=1;
		for(int i=0;i<G[x].size();++i){
			int nx=G[x][i].first,c=G[x][i].second;
			if(dis[nx]>dis[x]+c){
				dis[nx]=dis[x]+c;
				pq.push({-dis[nx],nx});
			}
		}
	}
	cout<<dis[0]+y-o[n].h;
	return 0;
}

悬2关。