记录编号	306775	评测结果	AAAAAAAAAAAA
题目名称	售票系统	最终得分	100
用户昵称	小e	是否通过	通过
代码语言	C++	运行时间	0.271 s
提交时间	2016-09-13 10:12:16	内存使用	3.34 MiB

//注意区间开闭! 
#include "cstdio"

int C, S, R; 
int Tmax[550000], lazy[250000];

inline void Read(int& a)
{
	a = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9') ch = getchar();
	while(ch >= '0' && ch <= '9'){
		a = a * 10 + ch - '0';
		ch = getchar();
	}
}

inline int GetMax(const int& a, const int& b)
{
	if(a > b) return a;
	return b;
}

inline void PushDown(const int& rt)
{
	const int lch = rt << 1, rch = (rt << 1) | 1;
	Tmax[lch] += lazy[rt]; Tmax[rch] += lazy[rt];
	lazy[lch] += lazy[rt]; lazy[rch] += lazy[rt];
	lazy[rt] = 0;
}

int QueryMax(const int& l, const int& r, const int& rt, const int& s, const int& t)
{
	if(s <= l && t >= r) return Tmax[rt];
	if(lazy[rt]) PushDown(rt);
	const int mid = (l + r) >> 1, lch = rt << 1, rch = (rt << 1) | 1;
	if(t <= mid) return QueryMax(l, mid, lch, s, t);
	else if(s >= mid+1) return QueryMax(mid+1, r, rch, s, t);
	return GetMax(QueryMax(l, mid, lch, s, mid), QueryMax(mid+1, r, rch, mid+1, t));
}

void Add(const int& l, const int& r, const int& rt, const int& s, const int& t, const int& num)
{
	if(s <= l && t >= r){
		Tmax[rt] += num;
		lazy[rt] += num;
		return;
	}
	const int mid = (l + r) >> 1, lch = rt << 1, rch = (rt << 1) | 1;
	if(t <= mid) Add(l, mid, lch, s, t, num);
	else if(s >= mid+1) Add(mid+1, r, rch, s, t, num);
	else{
		Add(l, mid, lch, s, mid, num);
		Add(mid+1, r, rch, mid+1, t, num);
	}
	Tmax[rt] = GetMax(Tmax[lch], Tmax[rch]);
}

int main()
{
 	freopen("railway.in", "r", stdin); freopen("railway.out", "w", stdout);
 	Read(C); Read(S); Read(R);
 	int s, t, num;
 	while(R--){
		Read(s); Read(t); Read(num);
		if(num + QueryMax(1, C, 1, s, t-1) <= S){
			puts("YES");
			Add(1, C, 1, s, t-1, num);
		}
		else puts("NO");
	}
 	fclose(stdin); fclose(stdout);
 	return 0;
}
/*
4 6 4
1 4 2
1 3 2
2 4 3
1 2 3

YES
YES
NO
NO
*/