Submission #503313

#	Time	Username	Problem	Language	Result	Execution time	Memory
503313		InternetPerson10	Wall (IOI14_wall)	C++17	100 / 100	1018 ms	234976 KiB

wall

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

using namespace std;

int BIG = 123456789;

vector<int> ans;

struct SegTree {
    int val = 0;
    int lx, rx, mid;
    int lb = 0, rb = BIG; // bounds
    SegTree *ls = nullptr, *rs = nullptr;
    SegTree(int l, int r) {
        lx = l;
        rx = r;
        mid = (lx + rx)/2;
        if(r - l > 1) {
            int mid = (l + r)/2;
            ls = new SegTree(l, mid);
            rs = new SegTree(mid, r);
        }
    }
    void updateRight(int k) { // Min value, pushes everything on the right
        if(k >= rb) return;
        val = min(val, k);
        if(k >= lb) {
            rb = k;
            return;
        }
        lb = rb = k;
    }
    void updateLeft(int k) { // Max value, pushes everything on the left
        if(k <= lb) return;
        val = max(val, k);
        if(k <= rb) {
            lb = k;
            return;
        }
        lb = rb = k;
    }
    void prop() {
        //cout << "Nice one " << lx << ' ' << rx << ' ' << lb << ' ' << rb << ' '<< val <<"\n";
        if(ls == nullptr) return;
        ls->updateLeft(lb); 
        ls->updateRight(rb);
        rs->updateLeft(lb); 
        rs->updateRight(rb);
        lb = 0; rb = BIG;
    }
    void setMin(int l, int r, int k) {
        prop();
        if(l >= rx || lx >= r) return;
        if(l <= lx && rx <= r) {
            updateRight(k);
            return;
        }
        ls->setMin(l, r, k);
        rs->setMin(l, r, k);
    }
    void setMax(int l, int r, int k) {
        prop();
        if(l >= rx || lx >= r) return;
        if(l <= lx && rx <= r) {
            updateLeft(k);
            return;
        }
        ls->setMax(l, r, k);
        rs->setMax(l, r, k);
    }
    void getAll() {
        prop();
        if(rx - lx == 1) {
            ans[lx] = val;
            return;
        }
        ls->getAll();
        rs->getAll();
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    int siz = 1;
    while(siz <= n) siz *= 2;
    SegTree st(0, siz);
    ans.resize(siz);
    for(int i = 0; i < k; i++) {
        //cout << "Doing " << i << '\n';
        if(op[i] == 2) st.setMin(left[i], right[i]+1, height[i]);
        if(op[i] == 1) st.setMax(left[i], right[i]+1, height[i]);
    }
    st.getAll();
    for(int i = 0; i < n; i++) finalHeight[i] = ans[i];
    return;
}

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