Submission #1032352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032352		vjudge1	Wall (IOI14_wall)	C++17	100 / 100	564 ms	138576 KiB

wall

#include "wall.h"

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

const int lim=2e6+100;

struct{
    struct{
        int rem=0,add=0;
        int last=0;
    }tree[4*lim];
    int ans[lim]{};
    int n;
    void push(int node,int l,int r){
        if(l==r){
            if(tree[node].last){
                ans[l]=max(ans[l],tree[node].add);
                ans[l]=min(ans[l],tree[node].rem);
            }else{
                ans[l]=min(ans[l],tree[node].rem);
                ans[l]=max(ans[l],tree[node].add);
            }
        }else{
            int child=node<<1;
            if(tree[node].last){
                tree[child].rem=max(tree[child].rem,tree[node].add);
                tree[child].add=max(tree[child].add,tree[node].add);
                tree[child].rem=min(tree[child].rem,tree[node].rem);
                tree[child].add=min(tree[child].add,tree[node].rem);
            }else{
                tree[child].rem=min(tree[child].rem,tree[node].rem);
                tree[child].add=min(tree[child].add,tree[node].rem);
                tree[child].rem=max(tree[child].rem,tree[node].add);
                tree[child].add=max(tree[child].add,tree[node].add);
            }
            tree[child].last=tree[node].last;
            child++;
            if(tree[node].last){
                tree[child].rem=max(tree[child].rem,tree[node].add);
                tree[child].add=max(tree[child].add,tree[node].add);
                tree[child].rem=min(tree[child].rem,tree[node].rem);
                tree[child].add=min(tree[child].add,tree[node].rem);
            }else{
                tree[child].rem=min(tree[child].rem,tree[node].rem);
                tree[child].add=min(tree[child].add,tree[node].rem);
                tree[child].rem=max(tree[child].rem,tree[node].add);
                tree[child].add=max(tree[child].add,tree[node].add);
            }
            tree[child].last=tree[node].last;
        }
        tree[node].rem=200000;
        tree[node].add=0;
    }
    int L,R;
    int TY,VAL;
    void update(int l,int r,int node){
        if(r<L||R<l)return;
        push(node,l,r);
        if(L<=l&&r<=R){
            if(TY){
                tree[node].add=VAL;
            }else{
                tree[node].rem=VAL;
            }
            tree[node].last=TY;
            return;
        }
        int mid=(l+r)>>1,child=node<<1;
        update(l,mid,child),update(mid+1,r,child|1);
    }
    void update(int l,int r,int val,int ty){
        L=l,R=r,VAL=val,TY=ty;
        update(0,n-1,1);
    }
    void walk(int l,int r,int node){
        push(node,l,r);
        if(l==r)return;
        int mid=(l+r)>>1,child=node<<1;
        walk(l,mid,child),walk(mid+1,r,child|1);
    }
}st;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    st.n=n;
    for(int i=0;i<k;i++){
        st.update(left[i],right[i],height[i],op[i]&1);
    }
    st.walk(0,n-1,1);
    for(int i=0;i<n;i++){
        finalHeight[i]=st.ans[i];
    }
}

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