제출 #17236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
17236		murat	벽 (IOI14_wall)	C++98	0 / 100	242 ms	111108 KiB

wall

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

#define sol (k + k)
#define sag (k + k + 1)

using namespace std;

const int N = 2e6 + 5;
const int inf = 1e9 + 7;

class node {
    public:
    int min, max, t;
    node() { min = -inf; max = inf; t = -1; }
} ST[N << 2];

int n, m, x, y, z, ans[N];

void upd_max(node &x, int t) {
    x.t = 0;
    x.max = max(x.max, t);
    x.min = max(x.min, t);
}
void upd_min(node &x, int t) {
    x.t = 1;
    x.max = min(x.max, t);
    x.min = min(x.min, t);
}

void push(int k) {
    if(ST[k].t == -1) return ;
    if(ST[k].t) {
        upd_max(ST[sol], ST[k].min);
        upd_max(ST[sag], ST[k].min);
        upd_min(ST[sol], ST[k].max);
        upd_min(ST[sag], ST[k].max);
    }
    else {
        upd_min(ST[sol], ST[k].max);
        upd_min(ST[sag], ST[k].max);
        upd_max(ST[sol], ST[k].min);
        upd_max(ST[sag], ST[k].min);
    }
    ST[k].t = -1;
}

void push_max(int k, int bas, int son, int x, int y, int t) {
    if(bas > y || son < x) return ;
    if(x <= bas && son <= y) {
        upd_max(ST[k], t);
        return ;
    }
    push(k);
    push_max(k + k, bas, (bas+son)/2, x, y, t);
    push_max(k + k + 1, (bas+son)/2+1, son, x, y, t);
}

void push_min(int k, int bas, int son, int x, int y, int t) {
    if(bas > y || son < x) return ;
    if(x <= bas && son <= y) {
        upd_min(ST[k], t);
        return ;
    }
    push(k);
    push_min(k + k, bas, (bas+son)/2, x, y, t);
    push_min(k + k + 1, (bas+son)/2+1, son, x, y, t);
}

void solve(int k, int bas, int son) {
    if(bas == son) {
        if(ST[k].t == -1);
        else if(ST[k].min == -inf || ST[k].max == inf) {
            if(ST[k].min == -inf && ST[k].max == inf) return ;
            if(ST[k].min == -inf) ans[bas] = ST[k].max;
            else ans[bas] = ST[k].min;
        }
        else if(ST[k].t == 0) ans[bas] = ST[k].min;
        else ans[bas] = ST[k].max;
        return ;
    }
    push(k);
    solve(sol, bas, (bas + son)/2);
    solve(sag, (bas + son)/2+1, son);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){

    ::n = n;

    for(int i = 0; i < k; i++) {
        if(op[i] == 1) push_max(1, 1, n, left[i]+1, right[i]+1, height[i]);
        else push_min(1, 1, n, left[i]+1, right[i]+1, height[i]);
        //for(int j = left[i]+1; j <= right[i]+1; j++)
        //if(op[i] == 1) push_max(1, 1, n, j, j, height[i]);
        //else push_min(1, 1, n, j, j, height[i]);
    }

    solve(1, 1, n);

    for(int i = 1; i <= n; i++)
        finalHeight[i-1] = ans[i];

    return;
}

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