oj.uz

답안 #17232

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
17232 2015-11-09T10:23:10 Z murat 벽 (IOI14_wall) C++
0 / 100
 233 ms 111108 KB 
#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;
    if(x.min <= t && t <= x.max) x.min = t;
    else if(x.max < t) x.min = x.max = t;
}
void upd_min(node &x, int t) {
    x.t = 1;
    if(x.min <= t && t <= x.max) x.max = t;
    else if(x.min > t) x.min = x.max = t;
}

void push(int k) {
    if(ST[k].t == -1) return ;
    if(ST[k].t) {
        upd_min(ST[sol], ST[k].min);
        upd_min(ST[sag], ST[k].min);
        upd_max(ST[sol], ST[k].max);
        upd_max(ST[sag], ST[k].max);
    }
    else {
        upd_max(ST[sol], ST[k].max);
        upd_max(ST[sag], ST[k].max);
        upd_min(ST[sol], ST[k].min);
        upd_min(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].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.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 103284 KB Output is correct
2 Correct 9 ms 103284 KB Output is correct
3 Incorrect 29 ms 103284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 103284 KB Output is correct
2 Correct 185 ms 111108 KB Output is correct
3 Incorrect 233 ms 106532 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 103284 KB Output is correct
2 Correct 16 ms 103284 KB Output is correct
3 Incorrect 21 ms 103284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 103284 KB Output is correct
2 Correct 10 ms 103284 KB Output is correct
3 Incorrect 16 ms 103284 KB Output isn't correct
4 Halted 0 ms 0 KB -