记录编号	326280	评测结果	AAAAAAAAAA
题目名称	区间权最大	最终得分	100
用户昵称	SOBER GOOD BOY	是否通过	通过
代码语言	C++	运行时间	1.640 s
提交时间	2016-10-21 07:07:33	内存使用	4.51 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int maxn=100000+100;

int N,M,R;

int C[maxn*4];

struct ask
{
   int l,r,data;
}A[maxn],B[maxn];

bool comp(ask a,ask b)
{if(a.r!=b.r)return a.r<b.r;
else return a.l<b.l;};

void up(int x,int data)
{
     for(;x;x-=(x&(-x)))
     C[x]=max(C[x],data);
}

int get(int x)
{
    int res=0;
    for(;x<=R;x+=(x&(-x)))
    {
      res=max(res,C[x]);
    }
   
    return res;
}
int Ans[maxn];

int main()
{
    freopen("max.in","r",stdin);
    freopen("max.out","w",stdout);
    scanf("%d%d",&N,&M);
    int ha=0;
    for(int i=1;i<=N;i++)scanf("%d%d%d",&A[i].l,&A[i].r,&A[i].data),ha=min(ha,A[i].l),R=max(R,A[i].r);
    for(int i=1;i<=M;i++)scanf("%d%d",&B[i].l,&B[i].r),B[i].data=i,R=max(R,B[i].r);
    sort(A+1,A+N+1,comp);
    sort(B+1,B+M+1,comp);
    for(int pos=1,i=1,j=1;pos<=R;pos++)
    {
        while(A[i].r==pos&&i<=N)up(A[i].l,A[i].data),++i;
        while(B[j].r==pos&&j<=M)Ans[B[j].data]=get(B[j].l),++j;    
    }
    for(int i=1;i<=M;i++)printf("%d\n",Ans[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}