记录编号	268261	评测结果	AAAAAAAAAAAA
题目名称	售票系统	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.123 s
提交时间	2016-06-12 12:16:24	内存使用	2.12 MiB

#include<cstdio>
#include<cctype>
#define lch(rt) rt<<1
#define rch(rt) rt<<1|1
int read(){
	char ch;int x;bool minus=false;
	while(ch=getchar(),!isdigit(ch)&&ch!='-');
	if(ch=='-'){
		minus=true;
		ch=getchar();
	}
	x=ch-'0';
	while(ch=getchar(),isdigit(ch))x=x*10+ch-'0';
	return minus?-x:x;
}
const int maxn=60005;
int Max[maxn<<2];
int lazy[maxn<<2];
int max(int a,int b){
	return a>b?a:b;
}
void pushdown(int rt){
	lazy[lch(rt)]+=lazy[rt];lazy[rch(rt)]+=lazy[rt];
	Max[lch(rt)]+=lazy[rt];Max[rch(rt)]+=lazy[rt];
	lazy[rt]=0;
}
void insert(int rt,int l,int r,int a,int b,int w){
	if(a<=l&&r<=b){
		Max[rt]+=w;
		lazy[rt]+=w;
		return;
	}
	pushdown(rt);
	int mid=(l+r)>>1;
	if(b>mid)insert(rch(rt),mid+1,r,a,b,w);
	if(a<=mid)insert(lch(rt),l,mid,a,b,w);
	Max[rt]=max(Max[lch(rt)],Max[rch(rt)]);
}
int querymax(int rt,int l,int r,int a,int b){
	if(a<=l&&r<=b)return Max[rt];
	pushdown(rt);
	int mid=(l+r)>>1;
	if(b<=mid)return querymax(lch(rt),l,mid,a,b);
	if(a>mid)return querymax(rch(rt),mid+1,r,a,b);
	return max(querymax(lch(rt),l,mid,a,b),querymax(rch(rt),mid+1,r,a,b));
}
int main(){
	freopen("railway.in","r",stdin);
	freopen("railway.out","w",stdout);
	int n=read()-1,S=read(),Q=read();
	int a,b,c,tmp;
	while(Q--){
		a=read();b=read();c=read();
		if(a>b){
			tmp=a;a=b;b=tmp;
		}
		if(querymax(1,1,n,a,b-1)+c>S)puts("NO");
		else{
			puts("YES");
			insert(1,1,n,a,b-1,c);
		}
	}
	fclose(stdin);fclose(stdout);
	return 0;
}