比赛 20120712 评测结果 AAAAAAAAAA
题目名称 区间权最大 最终得分 100
用户昵称 Sky_miner 运行时间 0.918 s
代码语言 C++ 内存使用 10.21 MiB
提交时间 2016-02-17 10:16:59
显示代码纯文本
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,temp,N;
const int max_1 = 200000 + 10;
const int max_2 = 100000 + 10;


struct node{			//二叉树 
	int fa,left,right;
	int Max;
}A[max_1<<1];	//二倍  


struct Node{			//线段树 
	int type,l,r,w;
	bool operator <(const Node&b)const{
		return (r<b.r) || (r==b.r && type < b.type );
	}
}B[max_1];
int map_arr[max_2]={0},ans[max_2]={0},Ans;


void Build(int now){	//递归建树 
	if(A[now].left==A[now].right){
		map_arr[A[now].left]=now;
		return;
	}
	int mid=(A[now].left+A[now].right)>>1;
	A[now <<1].left=A[now].left ; A[now <<1].right=mid;
	A[now<<1|1].left=mid+1  ; A[now<<1|1].right=A[now].right;
	Build(now<<1);Build(now<<1|1);
}


void find(int x,int ll,int rr){
	if( (ll <= A[x].left) && (rr >= A[x].right) ){
		if(Ans<A[x].Max) Ans=A[x].Max;
		return;
	}
	int mid=(A[x].left+A[x].right)>>1;
	if(mid >=ll && mid < rr){
		find(x<<1,ll,mid);
		find(x<<1|1,mid+1,rr);
	}
	else if(mid<ll) find(x<<1|1,ll,rr);
	else find(x<<1,ll,rr);
}


int main(){
	freopen("max.in","r",stdin);
	freopen("max.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		B[i].type=1;
		scanf("%d %d %d",&B[i].l,&B[i].r,&B[i].w);
		if(B[i].l>N) N=B[i].l;
	}
	for(int i=1;i<=m;i++){
		B[i+n].type=2; B[i+n].w=i;
		scanf("%d %d",&B[i+n].l,&B[i+n].r);
		if(B[i+n].l>N) N=B[i+n].l;
	}
	sort(B+1,B+(n+m+1));
	A[1].left=1;A[1].right=N;
	Build(1); temp=1; n+=m;
	for(int i=1;i<=n;i++){
		if(B[i].type==1){
			temp = map_arr[ B[i].l ];
			A[temp].Max = max(A[temp].Max,B[i].w);
			temp = temp >>1;
			while(temp){
				A[temp].Max=A[temp <<1].Max;
				if( A[temp].Max < A[temp <<1|1].Max )
				A[temp].Max = A[temp <<1|1].Max;
				temp = temp >>1;
			}
		}
		else{
			Ans=0;
			find(1,B[i].l,n);
			ans[B[i].w]=Ans;
		}
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}