Submission #18408

#	Time	Username	Problem	Language	Result	Execution time	Memory
18408		chan492811	Wall (IOI14_wall)	C++98	100 / 100	1069 ms	141724 KiB

wall

#include <algorithm>
#define INF 2100000000
using namespace std;
int n,m,tn=1;
struct data{
    int maxh,minh,l,r;
};
data tree[8000010];
void make_tree(int a){
    if(a>=tn) return;
    make_tree(a*2); make_tree(a*2+1);
    if(tree[a*2].l==0) return;
    if(tree[a*2+1].l==0){ tree[a]=tree[a*2]; return; }
    tree[a].l=tree[a*2].l; tree[a].r=tree[a*2+1].r;
}
void update_node(int flag,int a,int h){
    if(flag==1){
        tree[a].maxh=max(tree[a].maxh,h);
        tree[a].minh=max(tree[a].minh,h);
    }else{
        tree[a].maxh=min(tree[a].maxh,h);
        tree[a].minh=min(tree[a].minh,h);
    }
}
void update(int flag,int a,int l,int r,int h){
    if(tree[a].l==0 || tree[a].r<l || tree[a].l>r) return;
    if(tree[a].l>=l && tree[a].r<=r){
        update_node(flag,a,h);
    }else{
        update_node(1,a*2,tree[a].minh);
        update_node(2,a*2,tree[a].maxh);
        update_node(1,a*2+1,tree[a].minh);
        update_node(2,a*2+1,tree[a].maxh);
        tree[a].maxh=INF; tree[a].minh=0;
        update(flag,a*2,l,r,h); update(flag,a*2+1,l,r,h);
    }
}
void finalupdate(int a){
    if(tree[a].l==0 || a>=tn) return;
    update_node(1,a*2,tree[a].minh);
    update_node(2,a*2,tree[a].maxh);
    update_node(1,a*2+1,tree[a].minh);
    update_node(2,a*2+1,tree[a].maxh);
    tree[a].maxh=INF; tree[a].minh=0;
    finalupdate(a*2); finalupdate(a*2+1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    int i;
    while(tn<n)tn*=2;
    for(i=tn;i<tn+n;i++) tree[i].l=i-tn+1,tree[i].r=i-tn+1;
    make_tree(1);
    for(i=0;i<k;i++){
        update(op[i],1,left[i]+1,right[i]+1,height[i]);
    }
    finalupdate(1);
    for(i=tn;i<tn+n;i++) finalHeight[i-tn]=tree[i].maxh;
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39