1 条题解

  • 0
    @ 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
    上传者