比赛 区间问题练习 评测结果 AWEEWWWEWWAW
题目名称 售票系统 最终得分 16
用户昵称 FFF团 运行时间 0.283 s
代码语言 C++ 内存使用 2.38 MiB
提交时间 2017-04-21 20:39:29
显示代码纯文本
#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=60010; 
struct tree{
	int l,r,max,delta;
}a[2*maxn];
int c[maxn];
int maxx=-0x7fffffff;
int built(int k,int l,int r){
	a[k].l=l;
	a[k].r=r;
	if(l==r) a[k].max=c[l];
	else{
		built(2*k,l,(l+r)/2);
		built(2*k+1,(l+r)/2+1,r);
		a[k].max=max(a[2*k].max,a[2*k+1].max); 	
	}
}

int add(int k,int l,int r,int delta){
	if(l<=a[k].l&&a[k].r<=r){
		a[k].delta+=delta;
	}
	else{
		if(l<=(a[k].l+a[k].r)/2) add(2*k,l,r,delta);
		if(r>(a[k].l+a[k].r)/2) add(2*k+1,l,r,delta);
		//a[k].max=max(a[2*k].max+a[2*k].delta,a[2*k+1].max+a[2*k+1].delta);
	}
	//printf("%d %d %d %d\n",a[k].l,a[k].r,a[k].max,a[k].delta);
}

int query(int k,int l,int r){
	if(l<=a[k].l&&a[k].r<=r){
		a[k].max+=a[k].delta;
		a[k].delta=0;
		maxx=max(maxx,a[k].max);
	}
	else{
		if(l<=(a[k].l+a[k].r)/2){
			a[2*k].delta+=a[k].delta;
			a[2*k+1].delta+=a[k].delta;
			a[k].max+=a[k].delta;
			a[k].delta=0;
			query(2*k,l,r);
		}
		if(r>(a[k].l+a[k].r)/2){
			a[2*k].delta+=a[k].delta;
			a[2*k+1].delta+=a[k].delta;
			a[k].max+=a[k].delta; 
			a[k].delta=0;
			query(2*k+1,l,r);
		}
	}
	//printf("%d %d %d %d\n",a[k].l,a[k].r,a[k].max,a[k].delta);
}

int n,t,m,x,y,w;

int main()
{
	freopen("railway.in","r",stdin);
	freopen("railway.out","w",stdout);
	scanf("%d%d%d",&n,&t,&m);
	for(int i=1;i<=n;i++)c[i]=0;
	built(1,1,n);
	for(int i=1;i<=m;i++){
		maxx=-0x7fffffff;
		scanf("%d%d%d",&x,&y,&w);
		query(1,x,y-1);
		if(maxx+w<=t){
			add(1,x,y-1,w);
			printf("YES\n");
		}
		else printf("NO\n");
	}
	return 0;
}