记录编号	39493	评测结果	AAAAAAAAAA
题目名称	901.区间权最大	最终得分	100
用户昵称	Czb。	是否通过	通过
代码语言	C++	运行时间	1.995 s
提交时间	2012-07-12 14:30:16	内存使用	1.83 MiB

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<set>
 
using namespace std;
 
struct orz
{
    int x,y,z;
}a[100001];
 
struct aaa
{
    int x,y,num;
    bool flag;
    bool operator<(const aaa & other) const
    {
        if(y<other.y)
            return true;
        return false;
    }
};
 
int n,m,ans[100001];
 
multiset <aaa> s;
 
multiset <aaa> ::iterator p,it;
 
int cmp(const void *a,const void *b)
{
    return (*(orz *)b).z-(*(orz *)a).z;
}
 
int main()
{
    freopen("max.in","r",stdin);
    freopen("max.out","w",stdout);
    int i,x,y;aaa tmp;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
    qsort(a+1,n,sizeof(orz),cmp);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        tmp.num=i;tmp.x=x;tmp.y=y;
        s.insert(tmp);
    }
    tmp.x=0x7FFFFFFF;tmp.y=-1;
    s.insert(tmp);
    tmp.x=0x7FFFFFFF;tmp.y=tmp.x;
    s.insert(tmp);
    for(i=1;i<=n;i++)
    {
        tmp.y=a[i].y;
        for(it=s.lower_bound(tmp);it!=s.end();it++)
        {
            if((*it).x<=a[i].x)
            {
                ans[(*it).num]=a[i].z;
                p=it;it--;
                s.erase(p);
            }
        }
    }
    for(i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}