比赛 不准粘代码,必须自己写(HS除外) 评测结果 AAAAAAAAAA
题目名称 清理牛棚 最终得分 100
用户昵称 ShallowDream雨梨 运行时间 0.142 s
代码语言 C++ 内存使用 20.64 MiB
提交时间 2019-10-02 16:39:40
显示代码纯文本
    #include<bits/stdc++.h>
    using namespace std;
    const int inf=99999999;
     int n,q,w,f[300005];
    struct cow{int l,r,sum;}a[10005];
    struct tree{int l,r,sum;}tree[500000];
    int cmp(cow x,cow y){return x.r<y.r;}//shengxu
    void build(int root,int l,int r){
    	tree[root].l=l;
    	tree[root].r=r;tree[root].sum=99999999;
    	if(l==r){	return ;}
    	int mid=(l+r)/2;
    	build(root*2,l,mid);
    	build(root*2+1,mid+1,r);}
    	
    int ask(int root,int l,int r){
    	if(l<=tree[root].l&&r>=tree[root].r)return tree[root].sum;
    	int mid=(tree[root].l+tree[root].r)/2;
    	int ans=1<<30;
    	if(l<=mid)ans=min(ask(root*2,l,r),ans);
    	if(r>mid)ans=min(ask(root*2+1,l,r),ans);
    	return ans;
    }
    void change(int root,int x,int y){
    	if(tree[root].l==tree[root].r){
    		tree[root].sum=y;return;}
    	int mid=(tree[root].l+tree[root].r)/2;
    	if(x<=mid)change(root*2,x,y);
    	else change(root*2+1,x,y);
    	tree[root].sum=min(tree[root*2].sum,tree[root*2+1].sum);
    }
    int main(){
     	 freopen("clean.in","r",stdin);
    	freopen("clean.out","w",stdout);
    	ios::sync_with_stdio(false);
       cin>>n>>q>>w;
      for(int i=1;i<=w;i++)f[i]=inf;
     	f[q]=0;
       build(1,q,w);
       change(1,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);
       for(int i=1;i<=n;i++){
    	f[a[i].r]=min(f[a[i].r],
    	ask(1,a[i].l-1,a[i].r)+a[i].sum);
    	change(1,a[i].r,f[a[i].r]);
    	}
    	if(f[w]==inf)cout<<-1;
    	else cout<<f[w];
     
    	return 0;}