比赛 Segment Tree Competition 评测结果 AAAAAAAAAAAA
题目名称 售票系统 最终得分 100
用户昵称 YGOI_真神名曰驴蛋蛋 运行时间 0.101 s
代码语言 C++ 内存使用 0.35 MiB
提交时间 2016-08-28 19:03:40
显示代码纯文本
#include<stdio.h>
#define fo(s) freopen((s),"r",stdin)
#define fe(s) freopen((s),"w",stdout)
#define fpstd fclose(stdin);fclose(stdout);
inline int mid(const int&l,const int&r){return (l+r)>>1;}
inline int max(const int&a,const int&b){return a<b?b:a;}
const int MAXN = 60000+10;
struct Node{
	int val;
	int lazy;
	Node(){val=lazy=0;}
};
struct LineTree{
	Node save[MAXN<<2];
	void add(int root,int l,int r,int ansl,int ansr,int val){
		if(ansl<=l&&ansr>=r){
			save[root].val+=val;
			save[root].lazy+=val;
			return ;
		}GetNew(root);
		if(ansl<=mid(l,r))add(root<<1,l,mid(l,r),ansl,ansr,val);
		if(ansr> mid(l,r))add(root<<1|1,mid(l,r)+1,r,ansl,ansr,val);
		save[root].val=max(save[root<<1].val,save[root<<1|1].val);
	}
	int query(int root,int l,int r,int ansl,int ansr){
		if(ansl<=l&&ansr>=r)return save[root].val;
		GetNew(root);
		if(ansr<=mid(l,r))return query(root<<1,l,mid(l,r),ansl,ansr);
		if(ansl> mid(l,r))return query(root<<1|1,mid(l,r)+1,r,ansl,ansr);
		return max(query(root<<1,l,mid(l,r),ansl,ansr),query(root<<1|1,mid(l,r)+1,r,ansl,ansr));
	}
	void GetNew(int root){
		save[root<<1].lazy	+=save[root].lazy;
		save[root<<1].val	+=save[root].lazy;
		save[root<<1|1].lazy+=save[root].lazy;
		save[root<<1|1].val	+=save[root].lazy;
		save[root].lazy		 =0;
	}
}a;
int doing(){
	fo("railway.in");
	fe("railway.out");
	int s,t,k;
	int From,To,Times;
	scanf("%d%d%d",&s,&t,&k);
	for(int i=1;i<=k;++i){
		scanf("%d%d%d",&From,&To,&Times);
		if(a.query(1,1,s-1,From,To-1)+Times<=t){
			printf("YES\n");
			a.add(1,1,s-1,From,To-1,Times);
		}else printf("NO\n");
	}
	fpstd;
	return 0;
}
int popopopopopopopopopopopopopo=doing();
int main(){;}