比赛 |
Segment Tree Competition |
评测结果 |
AAAAAAAAAAAA |
题目名称 |
售票系统 |
最终得分 |
100 |
用户昵称 |
哒哒哒哒哒! |
运行时间 |
0.224 s |
代码语言 |
C++ |
内存使用 |
1.79 MiB |
提交时间 |
2016-08-28 19:03:30 |
显示代码纯文本
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-48;
ch=getchar();
}
return x*f;
}
const int maxn=240010;
int num[maxn],lazy[maxn];
int le,ri;
void updata(int rt){
int lc=rt*2,rc=rt*2+1;
num[lc]+=lazy[rt];
num[rc]+=lazy[rt];
lazy[lc]+=lazy[rt];
lazy[rc]+=lazy[rt];
lazy[rt]=0;
}
int query(int rt,int l,int r){
if(le<=l&&ri>=r) return num[rt];
updata(rt);
int mid=(l+r)/2;
if(ri<=mid) return query(rt*2,l,mid);
if(le>mid) return query(rt*2+1,mid+1,r);
return max(query(rt*2,l,mid),query(rt*2+1,mid+1,r));
}
void insert(int x,int rt,int l,int r){
if(le<=l&&ri>=r){
num[rt]+=x;
lazy[rt]+=x;
return;
}
int mid=(l+r)/2;
if(le<=mid) insert(x,rt*2,l,mid);
if(ri>mid) insert(x,rt*2+1,mid+1,r);
num[rt]=max(num[rt*2],num[rt*2+1]);
}
int main(){
freopen("railway.in","r",stdin);freopen("railway.out","w",stdout);
int n=read(),max_v=read(),m=read();
for(int i=1;i<=m;i++){
le=read(),ri=read()-1;
int x=read();
int left=query(1,1,n-1);
if(left+x<=max_v){
printf("YES\n");
insert(x,1,1,n-1);
}
else printf("NO\n");
}
fclose(stdin);fclose(stdout);
return 0;
}