记录编号	35077	评测结果	AAAAAAAAAAAA
题目名称	售票系统	最终得分	100
用户昵称	belong.zmx	是否通过	通过
代码语言	C++	运行时间	0.322 s
提交时间	2012-02-15 11:50:11	内存使用	3.01 MiB

#include <iostream>
#include <cstdlib>
#include <cstdio>
#define max(a,b) (a>b?a:b)

using namespace std;

struct point{int l,r,lc,rc,ma,pr;}p[120000];
int i,j,c,s,r,tot,st,en,co;

void build(int l,int r,int u)
{
    p[u].l=l;p[u].r=r;
    if (l==r){p[u].lc=-1;p[u].rc=-1;}
    else
    {
        tot++;p[u].lc=tot;build(l,(l+r)/2,tot);
        tot++;p[u].rc=tot;build((l+r)/2+1,r,tot);
    }
}

bool judge(int l,int r,int x,int u)
{
    if (l>p[u].r || r<p[u].l) return(true);
    else
    {
        if (p[u].l>=l&&p[u].r>=l&&p[u].l<=r&&p[u].r<=r)
        {
            if (p[u].ma+x>s) return(false);
            else return(true);
        }
        else
        {
            p[p[u].lc].pr+=p[u].pr;p[p[u].rc].pr+=p[u].pr;
            p[p[u].lc].ma+=p[u].pr;p[p[u].rc].ma+=p[u].pr;
            p[u].pr=0;p[u].ma=max(p[p[u].lc].ma,p[p[u].rc].ma);
            return(judge(l,r,x,p[u].lc)&&judge(l,r,x,p[u].rc));
        }
    }
}

void modify(int l,int r,int x,int u)
{
    if (!(r<p[u].l || l>p[u].r))
    {
        if (p[u].l>=l&&p[u].r>=l&&p[u].l<=r&&p[u].r<=r)
        {
            p[u].pr+=x;p[u].ma+=x;
        }
        else
        {
            p[p[u].lc].pr+=p[u].pr;p[p[u].rc].pr+=p[u].pr;
            p[p[u].lc].ma+=p[u].pr;p[p[u].rc].ma+=p[u].pr;
            p[u].pr=0;
            modify(l,r,x,p[u].lc);modify(l,r,x,p[u].rc);
            p[u].ma=max(p[p[u].rc].ma,p[p[u].lc].ma);
        }
    }
}

int main()
{
    freopen("railway.in","r",stdin);
    freopen("railway.out","w",stdout);
    scanf("%d%d%d\n",&c,&s,&r);
    build(1,c-1,0);
    for (i=0;i<r;i++)
    {
        scanf("%d%d%d\n",&st,&en,&co);
        if (judge(st,en-1,co,0))
        {
            modify(st,en-1,co,0);
            printf("YES\n");
        }
        else printf("NO\n");
    }
    //for (i=0;i<=tot;i++) printf("%d %d %d %d %d %d\n",p[i].l,p[i].r,p[i].lc,p[i].rc,p[i].pr,p[i].ma);
    return 0;
}