제출 #931078

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
931078		Art_ogo	벽 (IOI14_wall)	C++17	61 / 100	375 ms	31060 KiB

wall

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <algorithm>
#include <utility>
#include "wall.h"
using namespace std;

const int MAXN = 1e5+10;

int t[4*MAXN];
int modmn[4*MAXN], modmx[4*MAXN];

void build(int v, int tl, int tr){
    modmn[v] = 1e9;
    modmx[v] = -1e9;
    if(tl == tr){
        t[v] = 0;
        return;
    }
    int tm = (tl + tr) >> 1;
    build(v * 2, tl, tm);
    build(v * 2 + 1, tm + 1, tr);
}

void push(int v){
    if(v * 2 + 1 > 4*MAXN) return;
    if(modmn[v] != 1e9){
        t[v * 2] = min(t[v * 2], modmn[v]);
        modmn[v * 2] = min(modmn[v], modmn[v * 2]);
        modmx[v * 2] = min(modmn[v], modmx[v * 2]);
        t[v * 2 + 1] = min(t[v * 2 + 1], modmn[v]);
        modmn[v * 2 + 1] = min(modmn[v], modmn[v * 2 + 1]);
        modmx[v * 2 + 1] = min(modmn[v], modmx[v * 2 + 1]);
        modmn[v] = 1e9;
    }
    if(modmx[v] != -1e9){
        t[v * 2] = max(t[v * 2], modmx[v]);
        modmn[v * 2] = max(modmx[v], modmn[v * 2]);
        modmx[v * 2] = max(modmx[v], modmx[v * 2]);
        t[v * 2 + 1] = max(t[v * 2 + 1], modmx[v]);
        modmn[v * 2 + 1] = max(modmx[v], modmn[v * 2 + 1]);
        modmx[v * 2 + 1] = max(modmx[v], modmx[v * 2 + 1]);
        modmx[v] = -1e9;
    }
}

void updmx(int l, int r, int val, int v, int tl, int tr){
    if(tl >= l && tr <= r){
        t[v] = max(t[v], val);
        modmn[v] = max(modmn[v], val);
        modmx[v] = max(modmx[v], val);
        return;
    }
    if(tl > r || tr < l)
        return;
    push(v);
    int tm = (tl + tr) >> 1;
    updmx(l, r, val, v * 2, tl, tm);
    updmx(l, r, val, v * 2 + 1, tm + 1, tr);
}

void updmn(int l, int r, int val, int v, int tl, int tr){
    if(tl >= l && tr <= r){
        t[v] = min(t[v], val);
        modmn[v] = min(modmn[v], val);
        modmx[v] = min(modmx[v], val);
        return;
    }
    if(tl > r || tr < l)
        return;
    push(v);
    int tm = (tl + tr) >> 1;
    updmn(l, r, val, v * 2, tl, tm);
    updmn(l, r, val, v * 2 + 1, tm + 1, tr);
}

int get(int idx, int v, int tl, int tr){
    if(tl == tr)
        return t[v];
    push(v);
    int tm = (tl + tr) >> 1;
    if(idx <= tm)
        return get(idx, v * 2, tl, tm);
    else return get(idx, v * 2 + 1, tm + 1, tr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    build(1, 0, n - 1);
    for(int i = 0; i < k; i++)
        if(op[i] == 1)
            updmx(left[i], right[i], height[i], 1, 0, n - 1);
        else updmn(left[i], right[i], height[i], 1, 0, n - 1);
    for(int i = 0; i < n; i++)
        finalHeight[i] = get(i, 1, 0, n - 1);
    return;
}

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