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