记录编号	445259	评测结果	AAAAAAAAAAAA
题目名称	售票系统	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.719 s
提交时间	2017-09-05 17:20:55	内存使用	1.23 MiB

#include<bits/stdc++.h>
using namespace std;
int a[60005],b[60005],add[60005],n,w,m,mi[60005],len;
void change(int l,int c,int h){
	for(int i=l;i<=min(c,b[l]*len);i++){
		a[i]+=h;
		if(a[i]+add[b[i]]<mi[b[i]])mi[b[i]]=a[i]+add[b[i]];
	}
	if(b[l]!=b[c]){
		for(int i=(b[c]-1)*len+1;i<=c;i++){
			a[i]+=h;
			if(a[i]+add[b[i]]<mi[b[i]])mi[b[i]]=a[i]+add[b[i]];
		}
	}
	for(int i=b[l]+1;i<b[c];i++){
		add[i]+=h;
		mi[i]+=h;
	}
}
int q(int l,int c){
	int h=0x3fffffff;
	for(int i=l;i<=min(c,b[l]*len);i++)h=min(a[i]+add[b[i]],h);
	if(b[l]!=b[c]){
		for(int i=(b[c]-1)*len+1;i<=c;i++)h=min(a[i]+add[b[i]],h);
	}
	for(int i=b[l]+1;i<b[c];i++)h=min(h,mi[i]);
	return h;
}
int main()
{
	freopen("railway.in","r",stdin);
	freopen("railway.out","w",stdout);
//	freopen("1.txt","r",stdin);
	scanf("%d%d%d",&n,&w,&m);
	n--;
	len=sqrt(n)+1;
	for(int i=1;i<=n;i++){
		a[i]=w;
		b[i]=(i-1)/len+1;
		mi[b[i]]=w;
	}
	for(int i=1;i<=m;i++){
		int l,c,h;
		scanf("%d%d%d",&l,&c,&h);
		if(q(l,c-1)>=h){
			cout<<"YES"<<endl;
			change(l,c-1,-h);
		}
		else cout<<"NO"<<endl;
	}
	return 0;
}