比赛 |
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;
}