比赛 区间问题练习 评测结果 WWEEWWWEWWTA
题目名称 售票系统 最终得分 8
用户昵称 swttc 运行时间 1.291 s
代码语言 C++ 内存使用 1.47 MiB
提交时间 2017-04-21 20:34:18
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int INF=200000000;
int c,s,r,minv[121000],tic[61000],o1,d,n,addv[121000],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]+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)
{
	if(y>x)
	{
		int lc=o*2,rc=lc+1;
		minv[o]=min(minv[lc],minv[rc]);
	}
	minv[o]+=addv[o];
	return;
}
void add(int o,int x,int y)
{
	if(x==y) addv[o]=-n;
	else
	{
		int lc=o*2,rc=lc+1,m=x+(y-x)/2;
		if(m>=o) add(lc,x,m);
		if(m<d)  add(rc,m+1,y);
	}
	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;
		query(1,1,c);
		if(minn>=n)
		{
			printf("YES\n");
			//cout<<"minn"<<minn<<endl;
			//for(int j=1;j<=c*2+1;j++) cout<<"minv[j]"<<minv[j]<<endl;
		    add(1,o1,d);
		}
		else printf("NO\n");
	}
	return 0;
}