Submission #939737

#	Time	Username	Problem	Language	Result	Execution time	Memory
939737		asdasdqwer	Wall (IOI14_wall)	C++14	100 / 100	718 ms	69512 KiB

wall

#include "wall.h"

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


int le;
vector<int> lzMin, lzMax;
const int minConst = 1e9;
const int maxConst = 0;

void init (int sz) {
    le=1;
    while(le<sz)le*=2;
    lzMin.assign(2*le, minConst);
    lzMax.assign(2*le, maxConst);
}

void pushdown(int x) {
    if (lzMin[x] == minConst && lzMax[x] == maxConst) {
        return;
    }

    lzMin[2*x+1] = min(max(lzMax[x], lzMin[2*x+1]), lzMin[x]);
    lzMin[2*x+2] = min(max(lzMax[x], lzMin[2*x+2]), lzMin[x]);
    lzMax[2*x+1] = max(min(lzMin[x], lzMax[2*x+1]), lzMax[x]);
    lzMax[2*x+2] = max(min(lzMin[x], lzMax[2*x+2]), lzMax[x]);

    lzMin[x] = minConst;
    lzMax[x] = maxConst;
}

void setVal(int l, int r, int v, int x, int lx, int rx, bool isMax=false) {
    if (lx >= r || rx <= l) return;
    if (rx - lx == 1) {
        if (isMax) {
            if (lzMax[x] < v) {
                lzMax[x] = v;
            }

            if (lzMin[x] < v) {
                lzMin[x] = v;
            }
        }

        else {
            if (lzMin[x] > v) {
                lzMin[x] = v;
            }

            if (lzMax[x] > v) {
                lzMax[x] = v;
            }
        }

        return;
    }

    pushdown(x);
    
    if (lx >= l && rx <= r) {
        if (isMax) {
            if (lzMax[x] < v) {
                lzMax[x] = v;
            }

            if (lzMin[x] < v) {
                lzMin[x] = v;
            }
        }

        else {
            if (lzMin[x] > v) {
                lzMin[x] = v;
            }

            if (lzMax[x] > v) {
                lzMax[x] = v;
            }
        }
        return;
    }

    int m=(lx+rx)/2;
    setVal(l, r, v, 2*x+1, lx, m, isMax);
    setVal(l, r, v, 2*x+2, m, rx, isMax);
}

void setMax(int l, int r, int v) {
    setVal(l, r, v, 0, 0, le, true);
}

void setMin(int l, int r, int v) {
    setVal(l, r, v, 0, 0, le, false);
}

int get(int i, int x, int lx, int rx) {
    if (rx-lx==1) {
        return lzMax[x];
    }

    pushdown(x);
    int m=(lx+rx)/2;
    if (i<m)return get(i,2*x+1,lx,m);
    else return get(i,2*x+2,m,rx);
}

int get(int i) {
    return get(i,0,0,le);
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    init(n);
    
    for (int i=0;i<k;i++) {
        if (op[i] == 1) {
            setMax(left[i], right[i]+1, height[i]);
        }

        else {
            setMin(left[i], right[i]+1, height[i]);
        }
    }

    for (int i=0;i<n;i++) {
        finalHeight[i] = get(i);
    }
}

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