Submission #1062366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062366		Vedant18	Wall (IOI14_wall)	C++14	100 / 100	431 ms	69632 KiB

wall

#include<bits/stdc++.h>
using namespace std;

struct node{
    int lowrbnd=0;
    int upprbnd=1e6;
};

vector<node>sgt(1<<22);
void push(int v){
    auto upd=[&](int &ind){
        ind=min(ind,sgt[v].upprbnd);
        ind=max(ind,sgt[v].lowrbnd); 
    };
        upd(sgt[2*v].upprbnd);
        upd(sgt[2*v].lowrbnd);
        upd(sgt[2*v+1].lowrbnd);
        upd(sgt[2*v+1].upprbnd);
        sgt[v]=node();
}
void build(int v,int tl, int tr){
    if(tl==tr){
        sgt[v].lowrbnd=0;
        sgt[v].upprbnd=0;
    }
    else{
        int tm=(tl+tr)/2;
        build(2*v,tl,tm);
        build(2*v+1,tm+1,tr);
    }
}
void upd_rng(int v, int tl, int tr, int l, int r, int typ, int val){
    if(l>r){
        return ;
    }
    if(tl==l&&tr==r){
        if(typ==1){
            //max with-> lowerbound update
            sgt[v].lowrbnd=max(val,sgt[v].lowrbnd);
            sgt[v].upprbnd=max(val,sgt[v].upprbnd);
        }
        else{
            //upper bound
            sgt[v].lowrbnd=min(val,sgt[v].lowrbnd);
            sgt[v].upprbnd=min(val,sgt[v].upprbnd);
        }
    }
    else{
        push(v);
        int tm=(tl+tr)/2;
        upd_rng(2*v,tl,tm,l,min(r,tm),typ,val);
        upd_rng(2*v+1,tm+1,tr,max(tm+1,l),r,typ,val);
    }
}
void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[]){
    int N=(1<<21)-1;
    build(1,0,N);
    for(int i=0;i<k;i++){
        upd_rng(1,0,N,left[i],right[i],op[i],height[i]);
    }
    for(int v=1;v<(1<<21);v++){
        push(v);
    }
    for(int i=0;i<n;i++){
        finalHeight[i]=sgt[i+(1<<21)].lowrbnd;
    }
}

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