记录编号	300793	评测结果	AAAAAAAAAAAA
题目名称	售票系统	最终得分	100
用户昵称	农场主	是否通过	通过
代码语言	C++	运行时间	0.442 s
提交时间	2016-08-28 22:02:04	内存使用	65.14 MiB

#include<cstdio>
#include<algorithm>
#define u tree[x]
#define lc tree[x<<1]
#define rc tree[x<<1|1] 
using namespace std;
class poi{
public:
	int l,r;
	int max,add;
}tree[4000000];
int s[1000000];

void maketree(int x,int l,int r){
	u.l=l;
	u.r=r;
	u.add=0;
	u.max=0;
	if (l==r){
	}
	else{
		maketree(x<<1,l,l+r>>1);
		maketree(x<<1|1,(l+r>>1)+1,r);
	}
}
void add(int x,int l,int r,int t);
void downdate(int x);

int main(){
	freopen("railway.in","r",stdin);
	freopen("railway.out","w",stdout);
	int n,k,m;
	scanf("%d%d%d",&n,&k,&m);
	maketree(1,1,n);
	int s,t,d;
	for (int i=1;i<=m;i++){
		scanf("%d%d%d",&s,&t,&d);
		add(1,s,t-1,d);
		if (tree[1].max>k){
			add(1,s,t-1,-d);
			printf("NO\n");
		}
		else printf("YES\n");
	}
	return 0;
}
void add(int x,int l,int r,int t){
	if (l<=u.l&&u.r<=r){
		u.max+=t;
		u.add+=t;
	}
	else{
		if (l<=lc.r)add(x<<1,l,r,t);
		if (r>=rc.l)add(x<<1|1,l,r,t);
		if (u.add!=0) downdate(x);
		u.max=max(lc.max,rc.max);
	}
}

void downdate(int x){
	add(x<<1,lc.l,lc.r,u.add);
	add(x<<1|1,rc.l,rc.r,u.add);
	u.add=0;
	u.max=max(lc.max,rc.max);
}