比赛 |
区间问题练习 |
评测结果 |
AWEEWWWEWWAW |
题目名称 |
售票系统 |
最终得分 |
16 |
用户昵称 |
FFF团 |
运行时间 |
0.283 s |
代码语言 |
C++ |
内存使用 |
2.38 MiB |
提交时间 |
2017-04-21 20:39:29 |
显示代码纯文本
#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=60010;
struct tree{
int l,r,max,delta;
}a[2*maxn];
int c[maxn];
int maxx=-0x7fffffff;
int built(int k,int l,int r){
a[k].l=l;
a[k].r=r;
if(l==r) a[k].max=c[l];
else{
built(2*k,l,(l+r)/2);
built(2*k+1,(l+r)/2+1,r);
a[k].max=max(a[2*k].max,a[2*k+1].max);
}
}
int add(int k,int l,int r,int delta){
if(l<=a[k].l&&a[k].r<=r){
a[k].delta+=delta;
}
else{
if(l<=(a[k].l+a[k].r)/2) add(2*k,l,r,delta);
if(r>(a[k].l+a[k].r)/2) add(2*k+1,l,r,delta);
//a[k].max=max(a[2*k].max+a[2*k].delta,a[2*k+1].max+a[2*k+1].delta);
}
//printf("%d %d %d %d\n",a[k].l,a[k].r,a[k].max,a[k].delta);
}
int query(int k,int l,int r){
if(l<=a[k].l&&a[k].r<=r){
a[k].max+=a[k].delta;
a[k].delta=0;
maxx=max(maxx,a[k].max);
}
else{
if(l<=(a[k].l+a[k].r)/2){
a[2*k].delta+=a[k].delta;
a[2*k+1].delta+=a[k].delta;
a[k].max+=a[k].delta;
a[k].delta=0;
query(2*k,l,r);
}
if(r>(a[k].l+a[k].r)/2){
a[2*k].delta+=a[k].delta;
a[2*k+1].delta+=a[k].delta;
a[k].max+=a[k].delta;
a[k].delta=0;
query(2*k+1,l,r);
}
}
//printf("%d %d %d %d\n",a[k].l,a[k].r,a[k].max,a[k].delta);
}
int n,t,m,x,y,w;
int main()
{
freopen("railway.in","r",stdin);
freopen("railway.out","w",stdout);
scanf("%d%d%d",&n,&t,&m);
for(int i=1;i<=n;i++)c[i]=0;
built(1,1,n);
for(int i=1;i<=m;i++){
maxx=-0x7fffffff;
scanf("%d%d%d",&x,&y,&w);
query(1,x,y-1);
if(maxx+w<=t){
add(1,x,y-1,w);
printf("YES\n");
}
else printf("NO\n");
}
return 0;
}