比赛 |
20120712 |
评测结果 |
AAAAAAAAAA |
题目名称 |
区间权最大 |
最终得分 |
100 |
用户昵称 |
Sky_miner |
运行时间 |
0.918 s |
代码语言 |
C++ |
内存使用 |
10.21 MiB |
提交时间 |
2016-02-17 10:16:59 |
显示代码纯文本
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,temp,N;
const int max_1 = 200000 + 10;
const int max_2 = 100000 + 10;
struct node{ //二叉树
int fa,left,right;
int Max;
}A[max_1<<1]; //二倍
struct Node{ //线段树
int type,l,r,w;
bool operator <(const Node&b)const{
return (r<b.r) || (r==b.r && type < b.type );
}
}B[max_1];
int map_arr[max_2]={0},ans[max_2]={0},Ans;
void Build(int now){ //递归建树
if(A[now].left==A[now].right){
map_arr[A[now].left]=now;
return;
}
int mid=(A[now].left+A[now].right)>>1;
A[now <<1].left=A[now].left ; A[now <<1].right=mid;
A[now<<1|1].left=mid+1 ; A[now<<1|1].right=A[now].right;
Build(now<<1);Build(now<<1|1);
}
void find(int x,int ll,int rr){
if( (ll <= A[x].left) && (rr >= A[x].right) ){
if(Ans<A[x].Max) Ans=A[x].Max;
return;
}
int mid=(A[x].left+A[x].right)>>1;
if(mid >=ll && mid < rr){
find(x<<1,ll,mid);
find(x<<1|1,mid+1,rr);
}
else if(mid<ll) find(x<<1|1,ll,rr);
else find(x<<1,ll,rr);
}
int main(){
freopen("max.in","r",stdin);
freopen("max.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
B[i].type=1;
scanf("%d %d %d",&B[i].l,&B[i].r,&B[i].w);
if(B[i].l>N) N=B[i].l;
}
for(int i=1;i<=m;i++){
B[i+n].type=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].left=1;A[1].right=N;
Build(1); temp=1; n+=m;
for(int i=1;i<=n;i++){
if(B[i].type==1){
temp = map_arr[ B[i].l ];
A[temp].Max = max(A[temp].Max,B[i].w);
temp = temp >>1;
while(temp){
A[temp].Max=A[temp <<1].Max;
if( A[temp].Max < A[temp <<1|1].Max )
A[temp].Max = A[temp <<1|1].Max;
temp = temp >>1;
}
}
else{
Ans=0;
find(1,B[i].l,n);
ans[B[i].w]=Ans;
}
}
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}