제출 #1240174

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1240174		coderg	벽 (IOI14_wall)	C++20	100 / 100	562 ms	151612 KiB

wall

#include "wall.h"
#include <algorithm>
using namespace std;

const int MAXN = 2000005;
const int INF = 1e9;

struct Node {
    int min_val, max_val;
    int lazy_min, lazy_max;
    
    Node() {
        min_val = 0; max_val = INF;
        lazy_min = 0; lazy_max = INF;
    }
};

Node tree[4*MAXN];

void push_lazy(int node, int l, int r) {
    if (l == r) return;
    int newnode=node<<1;
    // propagate max operations
    if (tree[node].lazy_max != INF) {
        int val = tree[node].lazy_max;
        for (int child = 2*node+1; child <= 2*node+2; child++) {
            tree[child].max_val = min(tree[child].max_val, val);
            tree[child].min_val = min(tree[child].min_val, val);
            tree[child].lazy_max = min(tree[child].lazy_max, val);
            tree[child].lazy_min = min(tree[child].lazy_min, val);
        }
        tree[node].lazy_max = INF;
    }
    
    // propagate min operations
    if (tree[node].lazy_min != 0) {
        int val = tree[node].lazy_min;
        for (int child = 2*node+1; child <= 2*node+2; child++) {
            tree[child].max_val = max(tree[child].max_val, val);
            tree[child].min_val = max(tree[child].min_val, val);
            tree[child].lazy_max = max(tree[child].lazy_max, val);
            tree[child].lazy_min = max(tree[child].lazy_min, val);
        }
        tree[node].lazy_min = 0;
    }
}
// to limit the maximum height(op 2)
void update_max(int node, int l, int r, int a, int b, int val) {
    push_lazy(node, l, r);
    int newnode=node<<1;
    if (b < l || a > r) return;
    if (a <= l && r <= b) {
        tree[node].max_val = min(tree[node].max_val, val);
        tree[node].min_val = min(tree[node].min_val, val);
        tree[node].lazy_max = min(tree[node].lazy_max, val);
        tree[node].lazy_min = min(tree[node].lazy_min, val);
        return;
    }
    
    int m = (l + r) / 2;
    update_max(newnode+1, l, m, a, b, val);
    update_max(newnode+2, m+1, r, a, b, val);
    
    tree[node].min_val = min(tree[newnode+1].min_val, tree[newnode+2].min_val);
    tree[node].max_val = max(tree[newnode+1].max_val, tree[newnode+2].max_val);
}
//to set a minimum height(op 1)
void update_min(int node, int l, int r, int a, int b, int val) {
    push_lazy(node, l, r);
    int newnode=node<<1;
    if (b < l || a > r) return;
    if (a <= l && r <= b) {
        tree[node].max_val = max(tree[node].max_val, val);
        tree[node].min_val = max(tree[node].min_val, val);
        tree[node].lazy_max = max(tree[node].lazy_max, val);
        tree[node].lazy_min = max(tree[node].lazy_min, val);
        return;
    }
    
    int m = (l + r) / 2;
    update_min(newnode+1, l, m, a, b, val);
    update_min(newnode+2, m+1, r, a, b, val);
    
    tree[node].min_val = min(tree[newnode+1].min_val, tree[newnode+2].min_val);
    tree[node].max_val = max(tree[newnode+1].max_val, tree[newnode+2].max_val);
}

void build_final(int node, int l, int r, int finalHeight[]) {
    push_lazy(node, l, r);
    int newnode=node<<1;
    if (l == r) {
        finalHeight[l] = tree[node].min_val;
        return;
    }
    
    int mid = (l + r) / 2;
    build_final(newnode+1, l, mid, finalHeight);
    build_final(newnode+2, mid+1, r, finalHeight);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    
    for (int i = 0; i < 4*MAXN; i++) {
        tree[i] = Node();
    }
    
    
    for (int i = 0; i < k; i++) {
        if (op[i] == 1) { // add blocks (min height)
            update_min(0, 0, n-1, left[i], right[i], height[i]);
        } else { // remove blocks (max height)
            update_max(0, 0, n-1, left[i], right[i], height[i]);
        }
    }
    
    // build final heights
    build_final(0, 0, n-1, finalHeight);
}

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