Submission #1167968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167968		Godgift42	Wall (IOI14_wall)	C++20	100 / 100	606 ms	88976 KiB

wall

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

struct dt{
    int ma=1000000000;
    int mi=0;
};

vector<dt> st;

void psh(int v,int tl, int tr,int tm){
    st[v*2].mi=max(st[v*2].mi,st[v].mi);
    st[v*2].ma=max(st[v*2].mi,st[v*2].ma);
    st[v*2].ma=min(st[v*2].ma,st[v].ma);
    st[v*2].mi=min(st[v*2].ma,st[v*2].mi);
    st[v*2+1].mi=max(st[v*2+1].mi,st[v].mi);
    st[v*2+1].ma=max(st[v*2+1].mi,st[v*2+1].ma);
    st[v*2+1].ma=min(st[v*2+1].ma,st[v].ma);
    st[v*2+1].mi=min(st[v*2+1].ma,st[v*2+1].mi);
    st[v].mi=0;
    st[v].ma=1000000000;
}

void query(int v, int tl, int tr,int l, int r, int x, int h){
    if(l>r)return;
    if(l==tl and r==tr){
        if(x==1){
            st[v].mi=max(st[v].mi,h);
            st[v].ma=max(st[v].ma,h);
        }
        else{
            st[v].mi=min(st[v].mi,h);
            st[v].ma=min(st[v].ma,h);
        }
    }
    else{
        int tm=(tl+tr)/2;
        psh(v,tl,tr,tm);
        query(v*2,tl,tm,l,min(r,tm),x,h);
        query(v*2+1,tm+1,tr,max(l,tm+1),r,x,h);
    }
}

int get(int v, int tl, int tr, int pos){
    if(tl==tr){
        return st[v].mi;
    }
    int tm=(tl+tr)/2;
    psh(v,tl,tr,tm);
    if(pos<=tm)return get(v*2,tl,tm,pos);
    else return get(v*2+1,tm+1,tr,pos);
}

void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[]){
    st.resize(4*n);
    for(int i=0;i<k;i++){
        query(1,0,n-1,left[i],right[i],op[i],height[i]);
    }
    for(int i=0;i<n;i++){
        finalHeight[i]=get(1,0,n-1,i);
    }
}

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