记录编号	269038	评测结果	AAAAAAAAAA
题目名称	区间权最大	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	1.515 s
提交时间	2016-06-13 07:08:20	内存使用	4.81 MiB

#include<cstdio>
#include<cassert>
#include<algorithm>
using namespace std;
const int maxn=100005;
struct range{
	int l,r,w;
}inter[maxn];
bool cmp(const range &x,const range &y){
	return x.r<y.r;
}
struct node{
	int l,r,ans,pos;
}lst[maxn];
bool cmp1(const node &x,const node &y){
	return x.r<y.r;
}
bool cmp2(const node &x,const node &y){
	return x.pos<y.pos;
}
int max(int a,int b){
	return a>b?a:b;
}
int Max[800005];
void insert(int rt,int l,int r,int k,int w){
	if(l==r)Max[rt]=max(Max[rt],w);
	else{
		int mid=(l+r)>>1;
		if(k<=mid)insert(rt<<1,l,mid,k,w);
		else insert(rt<<1|1,mid+1,r,k,w);
		Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);
	}
}
int querymax(int rt,int l,int r,int a,int b){
	if(a<=l&&r<=b)return Max[rt];
	int mid=(l+r)>>1;
	if(b<=mid)return querymax(rt<<1,l,mid,a,b);
	if(a>mid)return querymax(rt<<1|1,mid+1,r,a,b);
	return max(querymax(rt<<1,l,mid,a,b),querymax(rt<<1|1,mid+1,r,a,b));
}
int main(){
	freopen("max.in","r",stdin);
	freopen("max.out","w",stdout);
	int n,m;scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d %d %d",&inter[i].l,&inter[i].r,&inter[i].w);
	}
	sort(inter+1,inter+n+1,cmp);
	int lim=inter[n].r;
	for(int i=1;i<=m;++i){
		scanf("%d %d",&lst[i].l,&lst[i].r);
		lst[i].pos=i;
	}
	sort(lst+1,lst+m+1,cmp1);
	lim=max(lim,lst[m].r);
	int pt=1;
	for(int i=1;i<=m;++i){
		if(lst[i].r==lst[i-1].r){
			lst[i].ans=querymax(1,1,lim,lst[i].l,lst[i].r);
		}else{
			for(;inter[pt].r<=lst[i].r&&pt<=n;pt++)insert(1,1,lim,inter[pt].l,inter[pt].w);
			lst[i].ans=querymax(1,1,lim,lst[i].l,lst[i].r);
		}
	}
	
	sort(lst+1,lst+m+1,cmp2);
	for(int i=1;i<=m;++i){
		printf("%d\n",lst[i].ans);
	}
	fclose(stdin);fclose(stdout);
	return 0;
}