记录编号	384636	评测结果	AAAAAAAAAAAA
题目名称	售票系统	最终得分	100
用户昵称	rvalue	是否通过	通过
代码语言	C++	运行时间	0.144 s
提交时间	2017-03-18 20:12:35	内存使用	5.78 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

const int INF=0x7FFFFFFF;
const int MAXN=60010;

struct Node{
	int l;
	int r;
	int max;
	int add;
	Node* lch;
	Node* rch;
};

Node N[MAXN<<2];
Node* top=N;

int c;
int s;
int l;
int r;
int add;

void Build(Node*,int,int);
void PushDown(Node*);
void Add(Node*);
int Query(Node*);
int Max(int,int);
void Swap(int&,int&);
void FastRead(int&);
void FastRead(long long&);

int main(){

#ifndef ASC_LOCAL
	freopen("railway.in","r",stdin);
	freopen("railway.out","w",stdout);
#endif
	int r;

	FastRead(c);
	FastRead(s);
	FastRead(r);
	Build(top++,1,c+1);
	for(int i=0;i<r;i++){
		FastRead(::l);
		FastRead(::r);
		FastRead(::add);
		// printf("o=%d d=%d\n",o,d);
		if(::l>::r)
			Swap(::l,::r);
		if(s-Query(N)>=add){
			puts("YES");
			Add(N);
		}
		else
			puts("NO");
	}
	return 0;
}

int Query(Node* root){
	// printf("l=%d,r=%d,root:l=%d,r=%d\n",l,r,root->l,root->r);
	if(l<=root->l&&root->r<=r)
		return root->max;
	else{
		PushDown(root);
		int ans=0;
		if(l<root->lch->r)
			ans=Max(ans,Query(root->lch));
		if(root->rch->l<r)
			ans=Max(ans,Query(root->rch));
		return ans;
	}
}

inline void PushDown(Node* root){
	root->rch->max+=root->add;
	root->rch->add+=root->add;
	root->lch->max+=root->add;
	root->lch->add+=root->add;
	root->add=0;
}

void Add(Node* root){
	if(l<=root->l&&root->r<=r){
		root->add+=add;
		root->max+=add;
	}
	else{
		if(root->add!=0)
			PushDown(root);
		if(l<root->lch->r)
			Add(root->lch);
		if(root->rch->l<r)
			Add(root->rch);
		root->max=Max(root->lch->max,root->rch->max);
	}
}

void Build(Node* root,int l,int r){
	root->l=l;
	root->r=r;
	if(r-l==1)
		return;
	else{
		int mid=(l+r)>>1;
		Build(root->lch=top++,l,mid);
		Build(root->rch=top++,mid,r);
	}
}

inline int Max(int a,int b){
	return a>b?a:b;
}

inline void Swap(int& a,int& b){
	a=a^b;
	b=a^b;
	a=a^b;
}

void FastRead(int& target){
	target=0;
	register char ch=getchar();
	while(ch>'9'||ch<'0')
		ch=getchar();
	while(ch<='9'&&ch>='0'){
		target=target*10+ch-48;
		ch=getchar();
	}
}

void FastRead(long long& target){
	target=0;
	register char ch=getchar();
	while(ch>'9'||ch<'0')
		ch=getchar();
	while(ch<='9'&&ch>='0'){
		target=target*10+ch-48;
		ch=getchar();
	}
}