Submission #1148814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148814		AlgorithmWarrior	Wall (IOI14_wall)	C++20	100 / 100	367 ms	59128 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

int const MAX=2e6+5;
int const INF=1e9;

struct node{
    int l,r;
    void intersect(node ot){
        if(r<ot.l)
            *this={ot.l,ot.l};
        else
            if(ot.r<l)
                *this={ot.r,ot.r};
            else
                *this={max(l,ot.l),min(r,ot.r)};
    }
};

struct AINT{
    node v[4*MAX];
    void init(int nod,int st,int dr){
        v[nod]={-INF,INF};
        if(st<dr){
            int mij=(st+dr)/2;
            init(2*nod,st,mij);
            init(2*nod+1,mij+1,dr);
        }
    }
    void propagate(int nod){
        v[2*nod].intersect(v[nod]);
        v[2*nod+1].intersect(v[nod]);
        v[nod]={-INF,INF};
    }
    void add(int nod,int st,int dr,int a,int b,int l,int r){
        if(a<=st && dr<=b)
            v[nod].intersect({l,r});
        else{
            propagate(nod);
            int mij=(st+dr)/2;
            if(a<=mij)
                add(2*nod,st,mij,a,b,l,r);
            if(b>mij)
                add(2*nod+1,mij+1,dr,a,b,l,r);
        }
    }
    void final_push(int nod,int st,int dr,int finalHeight[]){
        if(st==dr)
            finalHeight[st]=((v[nod].l>0)?v[nod].l:0);
        else{
            propagate(nod);
            int mij=(st+dr)/2;
            final_push(2*nod,st,mij,finalHeight);
            final_push(2*nod+1,mij+1,dr,finalHeight);
        }
    }
}aint;

void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
    aint.init(1,0,n-1);
    int i;
    for(i=0;i<k;++i){
        if(op[i]==1)
            aint.add(1,0,n-1,left[i],right[i],height[i],INF);
        else
            aint.add(1,0,n-1,left[i],right[i],-INF,height[i]);
    }
    aint.final_push(1,0,n-1,finalHeight);
}

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