比赛 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
}