比赛 Segment Tree Competition 评测结果 WWAWWWWWAWAA
题目名称 售票系统 最终得分 33
用户昵称 ZXCVBNM_1 运行时间 0.256 s
代码语言 C++ 内存使用 3.64 MiB
提交时间 2016-08-28 20:42:46
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define MAXN 60010
struct node
{
    int left,right,mn,tag;
}tree[MAXN*4];
int S;
int read()
{
    int s=0,fh=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')fh=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();}
    return s*fh;
}
void Pushup(int k){tree[k].mn=min(tree[k*2].mn,tree[k*2+1].mn);}
void Pushdown(int k)
{
    int l=k*2,r=k*2+1;
    if(tree[k].tag!=0)
    {
        tree[l].tag+=tree[k].tag;
        tree[r].tag+=tree[k].tag;
        tree[l].mn+=tree[k].tag;
        tree[r].mn+=tree[k].tag;
        tree[k].tag=0;
    }
}
void Build(int k,int l,int r)
{
    tree[k].left=l;tree[k].right=r;tree[k].tag=0;
    if(l==r){tree[k].mn=S;return;}
    int mid=(l+r)/2;
    Build(k*2,l,mid);
    Build(k*2+1,mid+1,r);
    Pushup(k);
}
int Query(int k,int ql,int qr)
{
    if(ql<=tree[k].left&&tree[k].right<=qr)return tree[k].mn;
    Pushdown(k);
    int mid=(tree[k].left+tree[k].right)/2;
    if(qr<=mid)return Query(k*2,ql,qr);
    else if(ql>mid)return Query(k*2+1,ql,qr);
    else return min(Query(k*2,ql,mid),Query(k*2+1,mid+1,qr));
    Pushup(k);
}
void Change(int k,int ql,int qr,int C)
{
    if(ql<=tree[k].left&&tree[k].right<=qr){tree[k].tag+=C;tree[k].mn+=C;return;}
    Pushdown(k);
    int mid=(tree[k].left+tree[k].right)/2;
    if(qr<=mid)Change(k*2,ql,qr,C);
    else if(ql>mid)Change(k*2+1,ql,qr,C);
    else {Change(k*2,ql,mid,C);Change(k*2+1,mid+1,qr,C);}
    Pushup(k);
}
int main()
{
    freopen("railway.in","r",stdin);
    freopen("railway.out","w",stdout);
    int C,R,s1,s2,s3,MN,i;
    C=read();S=read();R=read();
    Build(1,1,C);
    for(i=1;i<=R;i++)
    {
        s1=read();s2=read();s3=read();
        MN=Query(1,s1,s2);
        if(MN>=s3)
        {
            printf("YES\n");
            Change(1,s1,s2,-s3);
        }
        else printf("NO\n");
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}