求助WA on 11
查看原帖
求助WA on 11
659165
mysterys楼主2024/11/28 12:33

RT,

数据输出:5000000000

代码输出:4999500000

#include<bits/stdc++.h>
using namespace std;
#define FILE(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
#define int long long
#define endl '\n'
const int N=10005;
const int M=1e5+5;
struct node{
	int l,r,val;
}a[N];
int f[M];
#define ls u<<1
#define rs u<<1|1
int n,st,ed;
namespace T{
	int t[M<<2];
	inline void build(int u,int l,int r){
		if(l==r) return t[u]=f[l],void();
		int m=(l+r)>>1;
		build(ls,l,m);build(rs,m+1,r);
		t[u]=min(t[ls],t[rs]);
	}
	inline void upd(int u,int l,int r,int k,int v){
		if(l>k||r<k) return;
		if(l>=k&&r<=k) return t[u]=min(t[u],v),void();
		int m=(l+r)>>1;
		if(k<=m) upd(ls,l,m,k,v);
		else upd(rs,m+1,r,k,v); 
		t[u]=min(t[ls],t[rs]);
	}
	inline int ask(int u,int l,int r,int ql,int qr){
		if(l>qr||r<ql) return 1e18;
		if(l>=ql&&r<=qr) return t[u];
		int m=(l+r)>>1,res=1e18;
		if(ql<=m) res=ask(ls,l,m,ql,min(qr,m));
		if(qr>m) res=min(res,ask(rs,m+1,r,max(ql,m+1),qr));
		return res; 
	}
}
#undef ls
#undef rs
signed main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	cout.tie(nullptr);
	cin>>n>>st>>ed; 
	for(int i=1;i<=n;i++) cin>>a[i].l>>a[i].r>>a[i].val;
	for(int i=0;i<M;i++) f[i]=1e18;
	f[st]=0;
	T::build(1,st,ed);
	stable_sort(a+1,a+n+1,[&](node p1,node p2){
		return p1.r==p2.r?p1.l<p2.l:p1.r<p2.r;
	});
	for(int i=1;i<=n;i++){
		f[a[i].r]=min(f[a[i].r],T::ask(1,st,ed,max(a[i].l-1,st),min(a[i].r,ed))+a[i].val);
		T::upd(1,st,ed,min(a[i].r,ed),f[a[i].r]); 
		if(a[i].r>=ed) return cout<<(f[a[i].r]>=1e18?-1:f[a[i].r]),0;
	} 
	return 0;
}
2024/11/28 12:33
加载中...