1 条题解
-
0大金狮 (mengqingyu) LV 10 @ 2024-7-27 16:35:15
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #define N 10005 #define M 87000 using namespace std; const long long INF=10002 * 500004; int n,L,R; struct node { int a,b; long long c; }cow[N]; struct Node { int l,r; long long ans; }t[M*4]; inline bool cmp(node x,node y){ return x.a<y.a||(x.a==y.a)&&x.b<y.b; } void build(int p,int l,int r){ t[p].l=l;t[p].r=r;t[p].ans=INF; if(l==r)return ; int mid=(l+r)>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,r); } void change(int p,int l,long long val){ if(t[p].l==t[p].r){ t[p].ans=min(t[p].ans,val); return ; } int mid=(t[p].l+t[p].r)>>1; if(l<=mid)change(p<<1,l,val); if(l>mid)change(p<<1|1,l,val); t[p].ans=min(t[p].ans,min(t[p<<1].ans,t[p<<1|1].ans)); } long long ask(int p,int l,int r){ if(l==t[p].l&&r==t[p].r)return t[p].ans; int mid=(t[p].l+t[p].r)>>1; if(l>mid)return ask(p<<1|1,l,r); if(r<=mid)return ask(p<<1,l,r); return min(ask(p<<1,l,mid),ask(p<<1|1,mid+1,r)); } int main() { ios::sync_with_stdio(false); cin>>n>>L>>R; L++,R++; for(int i=1;i<=n;i++){ cin>>cow[i].a>>cow[i].b>>cow[i].c; cow[i].a++,cow[i].b++; } sort(cow+1,cow+1+n,cmp); build(1,L-1,R); change(1,L-1,0); for(int i=1;i<=n;i++){ change(1,cow[i].b,ask(1,cow[i].a-1,cow[i].b)+cow[i].c); } if(ask(1,R,R)==INF)cout<<-1<<endl; else cout<<ask(1,R,R)<<endl; return 0; }
- 1
信息
- ID
- 205
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 10
- 标签
- 递交数
- 8
- 已通过
- 4
- 上传者