比赛 |
Segment Tree Competition |
评测结果 |
AAAAAAAAAAAA |
题目名称 |
售票系统 |
最终得分 |
100 |
用户昵称 |
AntiLeaf |
运行时间 |
0.300 s |
代码语言 |
C++ |
内存使用 |
17.05 MiB |
提交时间 |
2016-08-28 19:02:46 |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lch l,mid,rt<<1
#define rch mid+1,r,rt<<1|1
using namespace std;
const int maxn=600010;
void update(int);
void add(int,int,int,int,int,int);
int query(int,int,int,int,int);
int a[maxn<<2],lazy[maxn<<2],n,mx,m,s,t,num;
int main(){
#define COGS
#ifdef COGS
freopen("railway.in","r",stdin);
freopen("railway.out","w",stdout);
#endif
scanf("%d%d%d",&n,&mx,&m);
memset(a,0,sizeof(int)*((n+5)<<2));
memset(lazy,0,sizeof(int)*((n+5)<<2));
for(int i=0;i<m;i++){
scanf("%d%d%d",&s,&t,&num);
if(query(s,t-1,1,n,1)+num>mx)printf("NO\n");
else{
printf("YES\n");
add(s,t-1,num,1,n,1);
}
}
#ifdef COGS
fclose(stdin);
fclose(stdout);
#endif
return 0;
}
void update(int rt){
int l=rt<<1,r=l|1;
a[l]+=lazy[rt];
a[r]+=lazy[rt];
lazy[l]+=lazy[rt];
lazy[r]+=lazy[rt];
lazy[rt]=0;
}
void add(int s,int t,int num,int l,int r,int rt){
if(s<=l&&t>=r){
a[rt]+=num;
lazy[rt]+=num;
return;
}
update(rt);
int mid=(l+r)>>1;
if(s<=mid)add(s,t,num,lch);
if(t>mid)add(s,t,num,rch);
a[rt]=max(a[rt<<1],a[rt<<1|1]);
}
int query(int s,int t,int l,int r,int rt){
if(s<=l&&t>=r)return a[rt];
update(rt);
int mid=(l+r)>>1;
if(t<=mid)return query(s,t,lch);
if(s>mid)return query(s,t,rch);
return max(query(s,t,lch),query(s,t,rch));
}