记录编号	201078	评测结果	AAAAAAAAAAAA
题目名称	售票系统	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.386 s
提交时间	2015-10-29 21:18:11	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
struct seg{
	int l,r;
	seg *lc,*rc;
	int delta;
	int sum;
	seg():sum(0),delta(0){}
};
int n,m,sum,ans;

seg *root=new seg;

void build_tree(int l,int r,seg*p){
	p->l=l; p->r=r;
	if (l+1==r){p->sum=sum;p->lc=NULL;p->rc=NULL;return;}
	else if (l+1<r){
		int mid=(l+r)>>1;
		p->lc=new seg;
		p->rc=new seg;
		if (l<mid) build_tree(l,mid,p->lc);
		if (mid<r) build_tree(mid,r,p->rc);
		p->sum=min(p->lc->sum,p->rc->sum);
	}
}

void update(seg *p){
	p->lc->sum-=p->delta;
	p->rc->sum-=p->delta;
	p->lc->delta+=p->delta;
	p->rc->delta+=p->delta;
	p->sum=min(p->lc->sum,p->rc->sum);
	p->delta=0;
}

void Q(int l,int r,seg*p){
	//cout<<l<<" "<<r<<" "<<p->l<<" "<<p->r<<endl;
	if (l<=p->l&&p->r<=r){
		if (p->delta&&p->l+1<p->r) update(p);
		ans=min(ans,p->sum);
	}else if (p->l+1<p->r){
		int mid=(p->l+p->r)>>1;
		if (p->delta) update(p);
		if (l<mid) Q(l,r,p->lc);
		if (mid<r) Q(l,r,p->rc);
		//p->sum=min(p->lc->sum,p->rc->sum);
	}
}

void change(int l,int r,int num,seg*p){
	if (l<=p->l&&p->r<=r){
		p->sum-=num;
		p->delta+=num;
		return;
	}else if (p->l+1<p->r){
		int mid=(p->l+p->r)>>1;
		if (p->delta) update(p);
		if (l<mid) change(l,r,num,p->lc);
		if (mid<r) change(l,r,num,p->rc);
		p->sum=min(p->lc->sum,p->rc->sum);
	}
}

int main(){
	freopen("railway.in","r",stdin);
	freopen("railway.out","w",stdout);
	scanf("%d%d%d",&n,&sum,&m);
	build_tree(1,n+1,root);
	for (int i=1;i<=m;++i){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		ans=sum; Q(x+1,y+1,root);
		//cout<<ans<<" "<<z<<endl;
		if (ans<z){
			printf("NO\n");
		}else{
			printf("YES\n");
			change(x+1,y+1,z,root);
		}
	}//system("pause");
	return 0;
}