比赛 |
Segment Tree Competition |
评测结果 |
AAAAAAAAAAAA |
题目名称 |
售票系统 |
最终得分 |
100 |
用户昵称 |
_Itachi |
运行时间 |
0.302 s |
代码语言 |
C++ |
内存使用 |
2.12 MiB |
提交时间 |
2016-08-28 19:02:49 |
显示代码纯文本
/*====================膜拜Tarjan==================*/
#include<stdio.h>
#define maxn 60050
#define fre freopen("railway.in","r",stdin);freopen("railway.out","w",stdout);
#define fcl fclose(stdin);fclose(stdout);
int _City,sum,tt;int e[maxn<<2],_lazy[maxn<<2];
int _max(const int &a,const int &b){return a>b?a:b;}
void _up(const int &rt){
if(!_lazy[rt])return ;
_lazy[rt<<1]+=_lazy[rt];
_lazy[rt<<1|1]+=_lazy[rt];
e[rt<<1]+=_lazy[rt];
e[rt<<1|1]+=_lazy[rt];
_lazy[rt]=0;
return;
}
int _sum(int rt,int l,int r,int s,int t){
if(l>r)return 0;
if(s<=l&&r<=t)return e[rt];_up(rt);
int mid=(l+r)>>1;
if(t<=mid)return _sum(rt<<1,l,mid,s,t);
if(mid<s)return _sum(rt<<1|1,mid+1,r,s,t);
//if(s<=mid||mid<t)
return _max(_sum(rt<<1,l,mid,s,t),_sum(rt<<1|1,mid+1,r,s,t));
}
void _add(int rt,int l,int r,int s,int t,int key){
if(l>r)return ;
if(s<=l&&r<=t){e[rt]+=key,_lazy[rt]+=key;return;}
int mid=(l+r)>>1;_up(rt);
if(t<=mid)_add(rt<<1,l,mid,s,t,key);
else if(mid<s) _add(rt<<1|1,mid+1,r,s,t,key);
else _add(rt<<1,l,mid,s,t,key),_add(rt<<1|1,mid+1,r,s,t,key);
e[rt]=_max(e[rt<<1],e[rt<<1|1]);/**/
return;
}
int main(){
fre
scanf("%d%d%d",&_City,&sum,&tt);
int s,t,n,tot;
while(tt--){
scanf("%d%d%d",&s,&t,&n);
if(s<1||t>_City||s>t||n>sum){puts("NO");continue;}
if(s==t){puts("YES");continue;}
tot=_sum(1,1,_City-1,s,t-1);
if(tot+n<=sum){puts("YES");_add(1,1,_City-1,s,t-1,n);}
else puts("NO");
}
fcl
}