比赛 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 ;
}