记录编号	398812	评测结果	AAAAAAAAAAAA
题目名称	售票系统	最终得分	100
用户昵称	swttc	是否通过	通过
代码语言	C++	运行时间	0.150 s
提交时间	2017-04-23 18:31:05	内存使用	2.38 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int INF=200000000;
int c,s,r,minv[241000],tic[61000],o1,d,n,addv[241000],minn;
void build(int o,int x,int y)
{
	if(x==y) minv[o]=tic[x];
	else
	{
		int lc=o*2,rc=lc+1,m=x+(y-x)/2;
		build(lc,x,m);
		build(rc,m+1,y);
		minv[o]=min(minv[lc],minv[rc]);
	}
	return;
}
void query(int o,int x,int y,int addo=0)
{
	if(x>=o1&&y<=d)  minn=min(minn,minv[o]+addo);//minn=min(minn,minv[o]+addv[o]+addo);?
	else
	{
		int lc=o*2,rc=lc+1,m=x+(y-x)/2;
		if(m>=o1) query(lc,x,m,addv[o]+addo);
		if(m<d)  query(rc,m+1,y,addv[o]+addo);
	}
	return;
}
void upit(int o,int x,int y)//add后进行当前节点更新 
{
	//system("pause");
	/*if(y>x)
	{
		int lc=o*2,rc=lc+1;
		minv[o]=min(minv[lc],minv[rc]);
	}
	minv[o]+=addv[o];
	return;*/
	if(x==y)
	{
		minv[o]+=addv[o];
		addv[o]=0;
	}
	else
	{
		int lc=o*2,rc=lc+1;
		minv[o]=min(minv[lc],minv[rc])+addv[o];
	}
	return;
}
void add(int o,int x,int y)
{
	if(x>=o1&&y<=d) addv[o]+=n;
	else
	{
		int lc=o*2,rc=lc+1,m=x+(y-x)/2;
		if(m>=o1) add(lc,x,m);
		if(m<d)  add(rc,m+1,y);
	}//system("pause");
	upit(o,x,y);
	return;
}
int main()
{
	freopen("railway.in","r",stdin);
	freopen("railway.out","w",stdout);
	scanf("%d%d%d",&c,&s,&r);
	for(int i=1;i<=c;i++) tic[i]=s;
	build(1,1,c);
	for(int i=1;i<=r;i++)
	{
		scanf("%d%d%d",&o1,&d,&n);
		minn=INF;
		d-=1;
		query(1,1,c);
		if(minn>=n)
		{
			n=-n;
			printf("YES");
			//cout<<"minn"<<minn<<endl;
			//for(int j=1;j<=c*4+1;j++) cout<<"minv[j]"<<minv[j]<<endl;
		    add(1,1,c);
		}
		else printf("NO");//,cout<<"minn"<<minn<<endl;
	}
	return 0;
}