比赛 |
不准粘代码,必须自己写(HS除外) |
评测结果 |
AAAAAAAAAA |
题目名称 |
清理牛棚 |
最终得分 |
100 |
用户昵称 |
梦那边的美好ET |
运行时间 |
0.108 s |
代码语言 |
C++ |
内存使用 |
17.86 MiB |
提交时间 |
2019-09-24 12:47:53 |
显示代码纯文本
#include<bits/stdc++.h>
#define maxn 100000
#define inf 1000000000
using namespace std;
int mi[maxn*4],lz[maxn*4];
void xc(int p){
mi[p*2]=min(mi[p*2],lz[p]);
mi[p*2+1]=min(mi[p*2+1],lz[p]);
lz[p*2]=min(lz[p*2],lz[p]);
lz[p*2+1]=min(lz[p*2+1],lz[p]);
lz[p]=inf;return;
}
void maketree(int p,int l,int r){
mi[p]=lz[p]=inf;
if(l==r)return;
int mid=(l+r)>>1;
maketree(p*2,l,mid);maketree(p*2+1,mid+1,r);
return;
}
void insert(int p,int l,int r,int l1,int r1,int x){
if(l1==l&&r1==r){lz[p]=min(lz[p],x);mi[p]=min(mi[p],x);return;}
int mid=(l+r)>>1;
if(r1<=mid)insert(p*2,l,mid,l1,r1,x);
if(mid<l1)insert(p*2+1,mid+1,r,l1,r1,x);
if(l1<=mid&&r1>mid)insert(p*2,l,mid,l1,mid,x),insert(p*2+1,mid+1,r,mid+1,r1,x);
return;
}
int getmin(int p,int l,int r,int x){
if(l==r)return mi[p];xc(p);
int mid=(l+r)>>1;
return (x<=mid)?getmin(p*2,l,mid,x):getmin(p*2+1,mid+1,r,x);
}
struct node{
int L,R,C;
bool operator<(const node &a1)const{return L<a1.L;}
}a[maxn];
int n,a1,a2,ans;
int main(){
freopen("clean.in","r",stdin);
freopen("clean.out","w",stdout);
scanf("%d%d%d",&n,&a1,&a2);
maketree(1,a1-1,a2);insert(1,a1-1,a2,a1-1,a1-1,0);
for(int i=1;i<=n;i++)scanf("%d%d%d",&a[i].L,&a[i].R,&a[i].C);
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)insert(1,a1-1,a2,a[i].L,a[i].R,a[i].C+getmin(1,a1-1,a2,a[i].L-1));
ans=getmin(1,a1-1,a2,a2);
if(ans==inf)printf("-1\n");
else printf("%d\n",ans);
return 0;
}