比赛 Segment Tree Competition 评测结果 AAAAAAAAAAAA
题目名称 售票系统 最终得分 100
用户昵称 Hzoi_Yniverse 运行时间 0.315 s
代码语言 C++ 内存使用 91.87 MiB
提交时间 2016-08-28 19:53:18
显示代码纯文本
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=6000100;
struct Node{
	int data,lazy;
}a[maxn*2];
void Insert(int,int,int,int,int,int);
int Qery(int,int,int,int,int);
void Updata(int);
int main(){
	freopen("railway.in","r",stdin);
	freopen("railway.out","w",stdout);
	int n,m,t;
	scanf("%d%d%d",&n,&m,&t);
	for(int i=1;i<=t;i++){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		int ans=Qery(x,y-1,1,1,n-1);
		if(m-ans>=z){
			printf("YES\n");
			Insert(x,y-1,z,1,1,n-1);
		}
		else printf("NO\n");
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}
void Insert(int s,int t,int x,int rt,int l,int r){
	if(s<=l&&t>=r){
		a[rt].data+=x;a[rt].lazy+=x;
		return;
	}
	Updata(rt);
	int mid=(l+r)>>1;
	if(s<=mid) Insert(s,t,x,rt<<1,l,mid);
	if(t>mid) Insert(s,t,x,rt<<1|1,mid+1,r);
	a[rt].data=max(a[rt<<1].data,a[rt<<1|1].data);
}
int Qery(int s,int t,int rt,int l,int r){
	if(s<=l&&t>=r){
		return a[rt].data;
	}
	Updata(rt);
	int mid=(l+r)>>1;
	int lson=0,rson=0;
	if(s<=mid) lson=Qery(s,t,rt<<1,l,mid);
	if(t>mid) rson=Qery(s,t,rt<<1|1,mid+1,r);
	return max(lson,rson);
}
void Updata(int x){
	int lala=a[x].lazy;
	a[x<<1].data+=lala;a[x<<1].lazy+=lala;
	a[x<<1|1].data+=lala;a[x<<1|1].lazy+=lala;
	a[x].lazy=0;
}