Submission #492732

#	Time	Username	Problem	Language	Result	Execution time	Memory
492732		Carmel_Ab1	Wall (IOI14_wall)	C++17	100 / 100	1220 ms	111628 KiB

wall

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


#include "wall.h"

const int maxn=4e6+1;

int t[2*maxn],L[2*maxn],R[2*maxn],propmx[2*maxn],propmn[2*maxn];




inline void build(int x,int tl,int tr){
    L[x]=tl;
    R[x]=tr;
    propmn[x]=1e9;
    propmx[x]=-1e9;
    if(tl+1==tr)return;

    int m=(L[x]+R[x])/2;
    build(2*x+1,tl,m);
    build(2*x+2,m,tr);
}

inline void applymn(int x,int v){
    propmx[x]=min(propmx[x],v);
    propmn[x]=min(propmn[x],v);
    t[x]=min(t[x],v);
}

inline void applymx(int x,int v){
    propmx[x]=max(propmx[x],v);
    propmn[x]=max(propmn[x],v);
    t[x]=max(t[x],v);
}

inline void push(int x){
    int lp=2*x+1,rp=2*x+2;

    applymn(lp,propmn[x]);
    applymn(rp,propmn[x]);
    propmn[x]=1e9;

    applymx(lp,propmx[x]);
    applymx(rp,propmx[x]);
    propmx[x]=-1e9;
}

inline void updmn(int x,int a,int b,int v){
    int l=L[x],r=R[x];
    if(r<=a || b<=l)
        return;
    else if(a<=l && r<=b){
        applymn(x,v);
        return;
    }
    push(x);
    updmn(2*x+1,a,b,v);
    updmn(2*x+2,a,b,v);
}
inline void updmx(int x,int a,int b,int v){
    int l=L[x],r=R[x];
    if(r<=a || b<=l)
        return;
    else if(a<=l && r<=b){
        applymx(x,v);
        return;
    }
    push(x);
    updmx(2*x+1,a,b,v);
    updmx(2*x+2,a,b,v);
}
inline int qur(int i,int x){
    int l=L[x],r=R[x];
    int m=(l+r)/2;
    if(l+1==r)
        return t[x];
    push(x);
    if(i<m)
        return qur(i,2*x+1);
    else
        return qur(i,2*x+2);
}

void buildWall(int n, int k, int op[], int LL[], int RR[], int H[], int ans[]){

    build(0,0,n);

    for(int i=0; i<k; i++){
        if(op[i]==1)
            updmx(0,LL[i],RR[i] +1,H[i]);
        else
            updmn(0,LL[i],RR[i] +1,H[i]);
    }
    for(int i=0; i<n; i++)
        ans[i]=qur(i,0);
}

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