比赛 20100324 评测结果 AAAWWWWWWWAA
题目名称 售票系统 最终得分 41
用户昵称 .Xmz 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-03-24 21:51:38
显示代码纯文本
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>

using namespace std;

struct node
{
	int a,b,m;
	node *l,*r;
	int maxv,delta;
}p[160001],*root;
int pn;
void mt(int a,int b,node *&k)
{
	pn++;
	k=p+pn;
	k->a=a; k->b=b; k->m=(a+b)/2;
	k->maxv=k->delta=0;
	if (a!=b)
	{
		mt(k->a,k->m,k->l);
		mt(k->m+1,k->b,k->r);
	}
}

int check(int a,int b,node *k)
{
	int da=0;
	if (k)
	{
		if (a <= k->a && k->b <= b) da=max(da,k->maxv);
		else if (b < k->a || k->b < a) return da;
		else
		{
			da=max(da,k->delta+check(a,b,k->l));
			da=max(da,k->delta+check(a,b,k->r));
		}
	}
	return da;
}

void edit(int a,int b,int n,node*&k)
{
	if (k)
	{
		if (a <= k->a && k->b <= b)   
		{	
			k->delta += n;
			k->maxv  += n;
		}
		else if (b < k->a || k->b < a) return;
		else
		{
			edit(a,b,n,k->l);
			edit(a,b,n,k->r);
		}
		if (k->l) if (k->maxv < k->l->maxv) k->maxv=k->l->maxv;
		if (k->r) if (k->maxv < k->r->maxv) k->maxv=k->r->maxv;
	}
}

int c,s,r;

int main()
{
	freopen("railway.in","r",stdin);
	freopen("railway.out","w",stdout);
	scanf("%d%d%d",&c,&s,&r);
	mt(1,c,root);
	int a,b,n,t;
	for (int i=1;i<=r;i++)
	{
		scanf("%d%d%d",&a,&b,&n);
		if (a<=b-1) 
		{
			t=check(a,b-1,root);
			if (t+n<=s)
			{
				printf("YES\n");
				edit(a,b-1,n,root);
			}
			else printf("NO\n");
		}
		else printf("YES\n"); 
	}
	return 0;
}