记录编号	543020	评测结果	AAWAAAAAAA
题目名称	[USACO Dec05]清理牛棚	最终得分	90
用户昵称	ShallowDream雨梨	是否通过	未通过
代码语言	C++	运行时间	0.137 s
提交时间	2019-10-02 16:22:49	内存使用	19.50 MiB

#include<bits/stdc++.h>
#define QWQ cout<<"qwq";
using namespace std;
const int maxn=10005;
const int inf=1500000000;
int f[maxn*100];
struct cow{int l,r,sum;}a[maxn];
bool cmp(cow a,cow b){return a.r<b.r;}
struct tree_{int sum;}tree[50*maxn];
void pushup(int root){
	tree[root].sum=min(tree[root<<1].sum,
	tree[root<<1|1].sum);}
void build(int root,int l,int r){
	tree[root].sum=inf;
	if(l==r)return ;
	int mid=(l+r)>>1;
	build(root<<1,l,mid);
	build(root<<1|1,mid+1,r);}
void add(int root,int l,int r,int x,int y){
	if(l==r){tree[root].sum=y;return ;}
	int mid=(l+r)>>1;
	if(x<=mid)add(root<<1,l,mid,x,y);
	else add(root<<1|1,mid+1,r,x,y);
	pushup(root);}
int ask(int root,int l,int r,int ql,int qr){
	if(l>=ql&&r<=qr)return tree[root].sum;
	int mid=(l+r)>>1;
	int ans=1<<30;
	if(ql<=mid)ans=min(ans,ask(root<<1,l,mid,ql,qr));
	if(qr>mid)ans=min(ans,ask(root<<1|1,mid+1,r,ql,qr));
	return ans;}
int main(){
	freopen("clean.in","r",stdin);
	freopen("clean.out","w",stdout);
	int n,q,w;
	cin>>n>>q>>w;
	for(int i=1;i<=w;i++)f[i]=inf;
	f[q]=0;
	for(int i=1;i<=n;i++)
	cin>>a[i].l>>a[i].r>>a[i].sum;
	sort(a+1,a+1+n,cmp);
	build(1,q,w);
	add(1,q,w,q,0);
	for(int i=1;i<=n;i++){
	f[a[i].r]=min(f[a[i].r],
	ask(1,q,w,a[i].l-1,a[i].r)+a[i].sum);
	add(1,q,w,a[i].r,f[a[i].r]);}
	if(f[a[n].r]==inf)cout<<-1;
	else cout<<f[a[n].r];
	return 0;
}