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

#include<cstdio>
#include<algorithm>
using namespace std;
inline void read(int &x){
	x=0;char ch;
	while(ch=getchar(),ch<'!');
	while(x=10*x+ch-'0',ch=getchar(),ch>'!');
}
const int maxn = 100000 + 10 ;
const int maxm = 200000 + 10;
inline int lowbit(int x){return x&-x;}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
int n,m,ans[maxn];
struct lne{
	int l,r,w;
}G[maxn];
struct cmd:lne{
	int pos;
}g[maxn];
inline bool cmp(const lne &a,const lne &b){ return a.l < b.l;}
inline bool kmp(const cmd &a,const cmd &b){ return a.l < b.l;}
int T[maxm],right ;
inline void add(int x,int w){while(x<=right) T[x]=cat_max(T[x],w),x+=lowbit(x);}
inline int Qmax(int x){
	int ret=0;
	while(x) ret=cat_max(T[x],ret),x-=lowbit(x);
	return ret;
}
int main(){
	freopen("max.in","r",stdin);
	freopen("max.out","w",stdout);
	read(n),read(m);
	for(int i=1;i<=n;++i){
		read(G[i].l),read(G[i].r),read(G[i].w);
		right=cat_max(right,G[i].r);
	} 
	sort(G+1,G+n+1,cmp);
	for(int i=1;i<=m;++i){
		read(g[i].l),read(g[i].r);g[i].pos=i;
		right = cat_max(right,g[i].r);
	} 
	sort(g+1,g+m+1,kmp);
	{
		int j = n , k = m;
		for(int i=right;i;--i){
			while(G[j].l==i){
				if(!j) break;
				add(G[j].r,G[j].w);
				--j;
			} 
			while(g[k].l==i){
				if( !k ) break;
				ans[g[k].pos] = Qmax(g[k].r);
				--k;
			} 
		}
	}
	for(int i=1;i<=m;++i)
		printf("%d\n",ans[i]);
	fclose(stdin);fclose(stdout);
	return 0;
}