比赛 20120712 评测结果 AAAAAAAAAA
题目名称 区间权最大 最终得分 100
用户昵称 沉迷学习的假的Keller 运行时间 0.964 s
代码语言 C++ 内存使用 10.23 MiB
提交时间 2016-02-17 09:57:39
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,i,zj1,zj2,zj3,N;
struct www{
    int typ,l,r,w;
    bool operator <(const www&b)const{
		return (r<b.r)||(r==b.r&&typ<b.typ);
	}
}B[200010];
int ret[100010]={0},ans[100010]={0},ANS;
struct wwww{int fa,L,R,Max;} A[400000];
inline void make(int now){
    if(A[now].L==A[now].R){
    	ret[A[now].L]=now;
    	return;
    }
    int mid=(A[now].L+A[now].R)>>1;
    A[now<<1].L=A[now].L,A[now<<1].R=mid;
    A[(now<<1)+1].L=mid+1,A[(now<<1)+1].R=A[now].R;
    make(now<<1);make((now<<1)+1);
}
inline void Findmax(int x,int ll,int rr){
    if((ll<=A[x].L)&&(rr>=A[x].R)){
		if(ANS<A[x].Max)
			ANS=A[x].Max;
		return;
	}
    int mid=(A[x].L+A[x].R)>>1;
	if(mid>=ll&&mid<rr){
		Findmax(x<<1,ll,mid);
		Findmax((x<<1)+1,mid+1,rr);
	}
    else if(mid<ll)Findmax((x<<1)+1,ll,rr);
    	else Findmax(x<<1,ll,rr);
}
int main(){
	freopen("max.in","r",stdin);
	freopen("max.out","w",stdout);
    scanf("%d%d",&n,&m);
   	for(i=1;i<=n;i++){
    	B[i].typ=1;
    	scanf("%d%d%d",&B[i].l,&B[i].r,&B[i].w);
   		if(B[i].l>N)N=B[i].l;
    }
    for(i=1;i<=m;i++){
    	B[i+n].typ=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].L=1,A[1].R=N;
   	make(1);
   	zj1=1;
   	for(n+=m,i=1;i<=n;i++){
   		if(B[i].typ==1){
   			zj1=ret[B[i].l];
    		A[zj1].Max=max(A[zj1].Max,B[i].w);
   			zj1>>=1;
   			while(zj1){
    			A[zj1].Max=A[zj1<<1].Max;
    			if(A[zj1].Max<A[(zj1<<1)+1].Max)
    			A[zj1].Max=A[(zj1<<1)+1].Max;
    			zj1>>=1;
    		}
    	}
    	else{
    		ANS=0;
    		Findmax(1,B[i].l,n);
    		ans[B[i].w]=ANS;
    	}
    }
    for(i=1;i<=m;i++)
		printf("%d\n",ans[i]);
    return 0;
}