Submission #763520

#	Time	Username	Problem	Language	Result	Execution time	Memory
763520		Ahmed57	Wall (IOI14_wall)	C++17	100 / 100	598 ms	103900 KiB

wall

#include <bits/stdc++.h>

using namespace std;
int seg[6000001];
void build(int p,int l,int r){
    if(l==r){
        seg[p] = 0;
        return ;
    }
    int md = (l+r)/2;
    build(p*2,l,md);build(p*2+1,md+1,r);
}
int li[6000001],ri[6000001];
void prop(int p,int l,int r){
    if(li[p]==-1)return ;
    //cout<<l<<" "<<r<<" "<<li[p]<<" "<<ri[p]<<endl;
    if(l==r){
        if(seg[p]<li[p]){
            seg[p] = li[p];
        }if(seg[p]>ri[p]){
            seg[p] = ri[p];
        }
    }
    if(l!=r){
        if(li[p*2]==-1){
            li[p*2] = li[p];
            ri[p*2] = ri[p];
        }else{
            if(ri[p*2]<li[p]){
                li[p*2] = li[p];
                ri[p*2] = li[p];
            }else if(ri[p]<li[p*2]){
                li[p*2] = ri[p];
                ri[p*2] = ri[p];
            }else{
                li[p*2] = max(li[p*2],li[p]);
                ri[p*2] = min(ri[p*2],ri[p]);
            }
        }
        if(li[p*2+1]==-1){
            li[p*2+1] = li[p];
            ri[p*2+1] = ri[p];
        }else{
            if(ri[p*2+1]<li[p]){
                li[p*2+1] = li[p];
                ri[p*2+1] = li[p];
            }else if(ri[p]<li[p*2+1]){
                li[p*2+1] = ri[p];
                ri[p*2+1] = ri[p];
            }else{
                li[p*2+1] = max(li[p*2+1],li[p]);
                ri[p*2+1] = min(ri[p*2+1],ri[p]);
            }
        }
    }
    li[p] = -1 , ri[p] = -1;
}
void update(int p,int l,int r,int lq,int rq,int ll,int rr){
    prop(p,l,r);
    if(l>=lq&&r<=rq){
        li[p]=ll;
        ri[p]=rr;
        prop(p,l,r);
        return ;
    }
    if(l>rq||r<lq)return ;
    int md = (l+r)/2;
    update(p*2,l,md,lq,rq,ll,rr);
    update(p*2+1,md+1,r,lq,rq,ll,rr);
}
vector<int> ans;
void dfs(int p,int l,int r){
    prop(p,l,r);
    if(l==r){
        ans.push_back(seg[p]);
        return ;
    }
    int md = (l+r)/2;
    dfs(p*2,l,md);
    dfs(p*2+1,md+1,r);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
    memset(li,-1,sizeof li);
    memset(ri,-1,sizeof ri);
    build(1,1,n);
    for(int i = 0;i<k;i++){
        if(op[i]==1){
            update(1,1,n,left[i]+1,right[i]+1,height[i],1e9);
        }else{
            update(1,1,n,left[i]+1,right[i]+1,0,height[i]);
        }
        ans.clear();
    }
    dfs(1,1,n);
    for(int i = 0;i<n;i++){
        finalHeight[i] = ans[i];
    }
}
/*
int main(){
    int op[] = {1,2,2,1,1,2};
    int height[] = {4,1,5,3,5,0};
    int left[] = {1,4,3,0,2,6};
    int right[] = {8,9,6,5,2,7};
    buildWall(10,6,op,left,right,height);
    return 0;
}
*/

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