제출 #856006

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
856006		ntkphong	벽 (IOI14_wall)	C++14	100 / 100	785 ms	99432 KiB

wall

#include "wall.h"
#include "bits/stdc++.h"
using namespace std;

const int inf = 1e9 + 1;

struct Node {
    int L, R;

    friend Node operator + (Node a, Node b) {
        Node c;

        c.L = max(a.L, b.L);
        c.R = min(a.R, b.R);

        if(c.L > c.R) {
            if(c.L == a.L) c.L = c.R;
            if(c.R == a.R) c.R = c.L;
        }

        return c;
    }
};

vector<Node> ST;

void down(int id) {
    Node x = ST[id];
    ST[id * 2] = ST[id * 2] + x;
    ST[id * 2 + 1] = ST[id * 2 + 1] + x;
    ST[id] = {0, inf};
}

void update(int id, int l, int r, int u, int v, Node x) {
    if(r < u || v < l) return ;

    if(u <= l && r <= v) {
        ST[id] = ST[id] + x;
        return ;
    }

    down(id);
    int mid = (l + r) / 2;
    update(id * 2, l, mid, u, v, x);
    update(id * 2 + 1, mid + 1, r, u, v, x);
}

Node get(int id, int l, int r, int x) {
    if(l == r) return ST[id];

    down(id);
    int mid = (l + r) / 2;
    if(x <= mid) {
        return get(id * 2, l, mid, x);
    } else {
        return get(id * 2 + 1, mid + 1, r, x);
    }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    ST.resize(4 * n + 4);
    for(int i = 1; i <= 4 * n; i ++) ST[i] = {0, inf};

    for(int i = 0; i < k; i ++) {
        Node x = {0, inf};

        if(op[i] == 1) x.L = height[i];
        if(op[i] == 2) x.R = height[i];

        update(1, 1, n, left[i] + 1, right[i] + 1, x);
    }

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

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