比赛 |
Segment Tree Competition |
评测结果 |
AAAAAAAAAAAA |
题目名称 |
售票系统 |
最终得分 |
100 |
用户昵称 |
农场主 |
运行时间 |
0.465 s |
代码语言 |
C++ |
内存使用 |
59.71 MiB |
提交时间 |
2016-08-28 22:02:12 |
显示代码纯文本
#include<cstdio>
#include<algorithm>
#define u tree[x]
#define lc tree[x<<1]
#define rc tree[x<<1|1]
using namespace std;
class poi{
public:
int l,r;
int max,add;
}tree[4000000];
int s[1000000];
void maketree(int x,int l,int r){
u.l=l;
u.r=r;
u.add=0;
u.max=0;
if (l==r){
}
else{
maketree(x<<1,l,l+r>>1);
maketree(x<<1|1,(l+r>>1)+1,r);
}
}
void add(int x,int l,int r,int t);
void downdate(int x);
int main(){
freopen("railway.in","r",stdin);
freopen("railway.out","w",stdout);
int n,k,m;
scanf("%d%d%d",&n,&k,&m);
maketree(1,1,n);
int s,t,d;
for (int i=1;i<=m;i++){
scanf("%d%d%d",&s,&t,&d);
add(1,s,t-1,d);
if (tree[1].max>k){
add(1,s,t-1,-d);
printf("NO\n");
}
else printf("YES\n");
}
return 0;
}
void add(int x,int l,int r,int t){
if (l<=u.l&&u.r<=r){
u.max+=t;
u.add+=t;
}
else{
if (l<=lc.r)add(x<<1,l,r,t);
if (r>=rc.l)add(x<<1|1,l,r,t);
if (u.add!=0) downdate(x);
u.max=max(lc.max,rc.max);
}
}
void downdate(int x){
add(x<<1,lc.l,lc.r,u.add);
add(x<<1|1,rc.l,rc.r,u.add);
u.add=0;
u.max=max(lc.max,rc.max);
}