제출 #235987

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
235987		Bilyana	벽 (IOI14_wall)	C++17	100 / 100	924 ms	115192 KiB

wall

#include<bits/stdc++.h>
#define f first
#define s second

using namespace std;

const int MAXA = 1e6;
vector<pair<int, int>> st;
vector<pair<int, int>> lp;

void findNewVal(pair<int, int> &l, pair<int, int> &r) {
    l.f = max(l.f, min(r.f, l.s));
    l.s = min(l.s, max(r.s, l.f));
}

void updateLazy(int curr, bool leaf, int pos) {
    if (leaf) {
        findNewVal(st[pos], lp[curr]);
        return;
    }
    findNewVal(lp[curr*2], lp[curr]);
    findNewVal(lp[curr*2+1], lp[curr]);
    lp[curr] = {0, MAXA};

}

void update(int curr, int l, int r, int b, int e, int val, int type) {
    updateLazy(curr, l==r, l);
    if (l > e || r < b) {
        return;
    }

    if (l >= b && r <= e) {
        if (type == 1) {
            lp[curr].f = min(lp[curr].s, val);
        } else if (type == 2) {
            lp[curr].s = max(lp[curr].f, val);
        }
        return;
    }
    int mid = (l+r)/2;
    update(curr*2, l, mid, b, e, val, type);
    update(curr*2+1, mid+1, r, b, e, val, type);
}

void calcAns(int curr, int l, int r) {
    //cerr<<l<<' '<<r<<" - "<<lp[curr].f<<' '<<lp[curr].s<<endl;
    updateLazy(curr, l==r, l);
    if (l == r) {
        return;
    }

    int mid = (l+r)/2;
    calcAns(curr*2, l, mid);
    calcAns(curr*2+1, mid+1, r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    st.resize(n, {0, MAXA}), lp.resize(4*n, {0, MAXA});
    for (int i=k-1; i>=0; i--) {
        update(1, 0, n-1, left[i], right[i], height[i], op[i]);
    }
    calcAns(1, 0, n-1);
    for (int i=0; i<n; i++) {
        finalHeight[i] = st[i].f;
    }
    return;
}

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