记录编号	465513	评测结果	AAAAAAAAAAAA
题目名称	售票系统	最终得分	100
用户昵称	WHZ0325	是否通过	通过
代码语言	C++	运行时间	0.166 s
提交时间	2017-10-27 10:24:16	内存使用	0.86 MiB

#include <cstdio>
#include <algorithm>
using namespace std;
const int inf=2147483647;
int st[150000];
void build(int o,int l,int r,int x) {
	st[o]=x;
	if(l==r) {
		return;
	}
	else {
		int mid=(l+r)>>1;
		build(o*2+1,l,mid,x);
		build(o*2+2,mid+1,r,x);
	}
}
int query(int o,int l,int r,int ql,int qr) {
	int ans=inf;
	if(ql<=l&&r<=qr) {
		return st[o];
	}
	else {
		int mid=(l+r)>>1;
		if(st[o]<min(st[o*2+1],st[o*2+2])) {
			int lazy=min(st[o*2+1],st[o*2+2])-st[o];
			st[o*2+1]-=lazy;
			st[o*2+2]-=lazy;
		}
		if(ql<=mid) {
			ans=min(ans,query(o*2+1,l,mid,ql,qr));
		}
		if(mid+1<=qr) {
			ans=min(ans,query(o*2+2,mid+1,r,ql,qr));
		}
	}
	return ans;
}
void update(int o,int l,int r,int ql,int qr,int x) {
	if(ql<=l&&r<=qr) {
		st[o]-=x;
	}
	else {
		int mid=(l+r)>>1;
		if(st[o]<min(st[o*2+1],st[o*2+2])) {
			int lazy=min(st[o*2+1],st[o*2+2])-st[o];
			st[o*2+1]-=lazy;
			st[o*2+2]-=lazy;
		}
		if(ql<=mid) {
			update(o*2+1,l,mid,ql,qr,x);
		}
		if(mid+1<=qr) {
			update(o*2+2,mid+1,r,ql,qr,x);
		}
		st[o]=min(st[o*2+1],st[o*2+2]);
	}
}
int main() {
	freopen("railway.in","r",stdin);
	freopen("railway.out","w",stdout);
	int c,s,r;
	scanf("%d%d%d",&c,&s,&r);
	build(0,1,c,s);
	int o,d,n;
	while(r--) {
		scanf("%d%d%d",&o,&d,&n);
		int out=query(0,1,c,o,d-1);
		if(out<n) {
			printf("NO\n");
		}
		else {
			update(0,1,c,o,d-1,n);
			printf("YES\n");
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}