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