比赛 |
Segment Tree Competition |
评测结果 |
AAAAAAAAAAAA |
题目名称 |
售票系统 |
最终得分 |
100 |
用户昵称 |
Sky_miner |
运行时间 |
0.167 s |
代码语言 |
C++ |
内存使用 |
1.69 MiB |
提交时间 |
2016-08-28 19:05:21 |
显示代码纯文本
#include <cstdio>
#include <algorithm>
#include <iostream>
const int maxn = 60000 + 10 ;
const int maxt = 180000+ 10 ;
char ch ;
inline void reader(int &ret) {
ret = 0 ; while (ch=getchar() , ch<'!') ;
while (ret=ret*10+ch-'0' , ch=getchar() , ch>'!') ;
}
inline int max(const int x,const int y){return x>y? x:y ;}
int N,C;
int l,r,Ret,add;
int G[maxt],lazy[maxt];
void Insert(int rt,int L,int R) {
if (l<=L && r>=R) lazy[rt] += add ;
else {
int mid = (L+R)>>1 ;
if (l <= mid) Insert(rt<<1,L ,mid) ;
if (r > mid) Insert(rt<<1|1,mid+1,R) ;
}
G[rt] = 0 ;
if (R > L) G[rt] = max(G[rt<<1],G[rt<<1|1]) ;
G[rt] += lazy[rt];
}
void Qer(int rt, int L , int R , int lazy_) {
if (l<=L && r>=R) Ret = max(Ret,G[rt]+lazy_) ;
else {
int mid = (L+R)>>1;
if(l <= mid) Qer(rt<<1 , L , mid , lazy_+lazy[rt]) ;
if(r > mid) Qer(rt<<1|1 , mid+1 , R , lazy_+lazy[rt]) ;
}
}
int main() {
freopen("railway.in" ,"r",stdin ) ;
freopen("railway.out","w",stdout) ;
int times;
reader(N);reader(C);reader(times);
while(times--){
reader(l),reader(r),reader(add);
r--;Ret=0;
Qer(1,1,N,0);
if(C-Ret < add){putchar('N');putchar('O');putchar('\n');}
else {putchar('Y');putchar('E');putchar('S');putchar('\n');Insert(1,1,N);}
}
return 0 ;
}