记录编号	586379	评测结果	AAAAAAAAAA
题目名称	[USACO Dec05]清理牛棚	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2024-01-17 20:54:42	内存使用	0.00 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+10,M = 1e4+10;
const ll inf = 1e17;
int n,L,R;
struct made{
    int l,r;ll z;
    bool operator < (made x)const{
        return r < x.r;
    }
}a[M];
ll f[N];
struct segment_tree{
    ll mi[N<<3];
    void update(int p) {
        mi[p] = min(mi[p<<1],mi[p<<1|1]);
    }
    void build(int p,int l,int r){
        mi[p] = inf;
        if(l == r)return;
        int mid = l + r >> 1;
        build(p<<1,l,mid),build(p<<1|1,mid+1,r);
    }
    void modify(int p,int l,int r,int L,ll z){
        if(l == r){mi[p] = z;return;}
        int mid = l + r >> 1;
        if(L <= mid)modify(p<<1,l,mid,L,z);
        else modify(p<<1|1,mid+1,r,L,z);
        update(p);
    }
    ll ask(int p,int l,int r,int L,int R){
        if(L <= l && r <= R)return mi[p];
        int mid = l + r >> 1;
        if(R <= mid)return ask(p<<1,l,mid,L,R);
        else if(L > mid)return ask(p<<1|1,mid+1,r,L,R);
        else return min(ask(p<<1,l,mid,L,R),ask(p<<1|1,mid+1,r,L,R));
    }
}T;
int main(){
    freopen("clean.in","r",stdin);
    freopen("clean.out","w",stdout);
    scanf("%d%d%d",&n,&L,&R);
    L++,R++;
    for(int i = 1;i <= n;i++)scanf("%d%d%lld",&a[i].l,&a[i].r,&a[i].z);
    sort(a+1,a+1+n);
    T.build(1,0,R);
    T.modify(1,0,R,L-1,0);
    for(int i = 1;i <= R;i++)f[i] = inf;
    for(int i = 1;i <= n;i++){
        int l = a[i].l,r = a[i].r;
        l++,r++;
        if(r < L)continue;
        f[r] = min(f[r],T.ask(1,0,R,l-1,r-1)+a[i].z);
        T.modify(1,0,R,r,f[r]);
    }
    if(f[R] == inf)printf("-1\n");
    else printf("%lld\n",f[R]);
    
    return 0;
    
}