比赛 |
Segment Tree Competition |
评测结果 |
AAAAAAAAAAAA |
题目名称 |
售票系统 |
最终得分 |
100 |
用户昵称 |
YGOI_真神名曰驴蛋蛋 |
运行时间 |
0.101 s |
代码语言 |
C++ |
内存使用 |
0.35 MiB |
提交时间 |
2016-08-28 19:03:40 |
显示代码纯文本
#include<stdio.h>
#define fo(s) freopen((s),"r",stdin)
#define fe(s) freopen((s),"w",stdout)
#define fpstd fclose(stdin);fclose(stdout);
inline int mid(const int&l,const int&r){return (l+r)>>1;}
inline int max(const int&a,const int&b){return a<b?b:a;}
const int MAXN = 60000+10;
struct Node{
int val;
int lazy;
Node(){val=lazy=0;}
};
struct LineTree{
Node save[MAXN<<2];
void add(int root,int l,int r,int ansl,int ansr,int val){
if(ansl<=l&&ansr>=r){
save[root].val+=val;
save[root].lazy+=val;
return ;
}GetNew(root);
if(ansl<=mid(l,r))add(root<<1,l,mid(l,r),ansl,ansr,val);
if(ansr> mid(l,r))add(root<<1|1,mid(l,r)+1,r,ansl,ansr,val);
save[root].val=max(save[root<<1].val,save[root<<1|1].val);
}
int query(int root,int l,int r,int ansl,int ansr){
if(ansl<=l&&ansr>=r)return save[root].val;
GetNew(root);
if(ansr<=mid(l,r))return query(root<<1,l,mid(l,r),ansl,ansr);
if(ansl> mid(l,r))return query(root<<1|1,mid(l,r)+1,r,ansl,ansr);
return max(query(root<<1,l,mid(l,r),ansl,ansr),query(root<<1|1,mid(l,r)+1,r,ansl,ansr));
}
void GetNew(int root){
save[root<<1].lazy +=save[root].lazy;
save[root<<1].val +=save[root].lazy;
save[root<<1|1].lazy+=save[root].lazy;
save[root<<1|1].val +=save[root].lazy;
save[root].lazy =0;
}
}a;
int doing(){
fo("railway.in");
fe("railway.out");
int s,t,k;
int From,To,Times;
scanf("%d%d%d",&s,&t,&k);
for(int i=1;i<=k;++i){
scanf("%d%d%d",&From,&To,&Times);
if(a.query(1,1,s-1,From,To-1)+Times<=t){
printf("YES\n");
a.add(1,1,s-1,From,To-1,Times);
}else printf("NO\n");
}
fpstd;
return 0;
}
int popopopopopopopopopopopopopo=doing();
int main(){;}