记录编号	406124	评测结果	AAAAAAAAAAAA
题目名称	售票系统	最终得分	100
用户昵称	沧澜	是否通过	通过
代码语言	C++	运行时间	1.004 s
提交时间	2017-05-17 21:13:46	内存使用	4.13 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int c,s,r,x,y,v;
struct haha{
    int maxx;
    int delta;
}tree[500000];
void updata(int left,int right,int root){
    int mid;
    if((y<left||x>right))
        return;
    if(x<=left&&y>=right){
        tree[root].maxx+=v;
        tree[root].delta+=v;
        return;
    }
    mid=(left+right)/2;
    int del=tree[root].delta;
    tree[root*2].delta+=del; tree[root*2].maxx+=del;
    tree[root*2+1].delta+=del; tree[root*2+1].maxx+=del;
    tree[root].delta=0;
    updata(left,mid,root*2);
    updata(mid+1,right,root*2+1);
    tree[root].maxx=max(tree[root*2].maxx,tree[root*2+1].maxx);
}
int search(int left,int right,int root){
    int mid,templ,tempr;
    if(x>right||y<left)
        return -200000;
    if(x<=left&&right<=y)
        return tree[root].maxx;
    mid=(left+right)/2;
    int del=tree[root].delta;
    tree[root*2].delta+=del; tree[root*2].maxx+=del;
    tree[root*2+1].delta+=del; tree[root*2+1].maxx+=del;
    tree[root].delta=0;
    templ=search(left,mid,root*2);
    tempr=search(mid+1,right,root*2+1);
    return max(templ,tempr);
}
int main(){
    freopen("railway.in","r",stdin);
    freopen("railway.out","w",stdout);
    cin>>c>>s>>r;
    for(int i=1;i<=r;i++){
        int o,d,n;
        cin>>o>>d>>n;
        x=o;
        y=d-1;
        v=n;
        updata(1,c,1);
        int t=search(1,c,1);
        if(t<=s)
            cout<<"YES"<<endl;
        else{
            cout<<"NO"<<endl;
            v=-n;
            updata(1,c,1);//把不合法的售票请求去掉
        }
    }
    return 0;
}