比赛 不准粘代码,必须自己写(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;
}