比赛 |
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;
}