比赛 Segment Tree Competition 评测结果 AAAAAAAAAAAA
题目名称 售票系统 最终得分 100
用户昵称 森林 运行时间 0.190 s
代码语言 C++ 内存使用 2.14 MiB
提交时间 2016-08-28 19:04:19
显示代码纯文本
#include<iostream>
#include<stdio.h>
#define fastcall __attribute__((optimize("-O3")))
using namespace std;
const int maxn=60010;
int tree[maxn<<2]={0},lazy[maxn<<2]={0};
fastcall inline int QR(){
	char ch;
	while(ch=getchar(),ch<'0'||ch>'9');
	int x=ch-48;
	while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;
	return x;
}
fastcall inline void update(int rt){
	tree[rt<<1]+=lazy[rt];
	tree[rt<<1|1]+=lazy[rt];
	lazy[rt<<1]+=lazy[rt];
	lazy[rt<<1|1]+=lazy[rt];
	lazy[rt]=0;
}
fastcall void Build(int l,int r,int s,int t,int rt,int jia){
	if(s>=l&&r>=t){
		tree[rt]+=jia;
		lazy[rt]+=jia;
		return;
	}
	int mid=(s+t)>>1;
	if(l<=mid)Build(l,r,s,mid,rt<<1,jia);
	if(r>mid)Build(l,r,mid+1,t,rt<<1|1,jia);
	tree[rt]=max(tree[rt<<1],tree[rt<<1|1]);
}
fastcall int Query(int l,int r,int s,int t,int rt){
	if(s>=l&&r>=t)return tree[rt];
	int mid=(s+t)>>1;
	if(lazy[rt])update(rt);
	if(r<=mid)return Query(l,r,s,mid,rt<<1);
	if(l>mid)return Query(l,r,mid+1,t,rt<<1|1);
	return max(Query(l,r,s,mid,rt<<1),Query(l,r,mid+1,t,rt<<1|1));
}
int main(){
	freopen("railway.in","r",stdin);
	freopen("railway.out","w",stdout);
	int c,s,r,o,d,n;
	c=QR(),s=QR(),r=QR();
	for(int g=1;g<=r;g++){
		o=QR(),d=QR(),n=QR();
		if(s-Query(o,d-1,1,c,1)>=n){
			puts("YES");
			Build(o,d-1,1,c,1,n);
		}
		else puts("NO");
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}