oj.uz

Submission #17236

# Submission time Handle Problem Language Result Execution time Memory
17236 2015-11-09T12:56:58 Z murat Wall (IOI14_wall) C++
0 / 100
 242 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;
    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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 103284 KB Output is correct
2 Correct 13 ms 103284 KB Output is correct
3 Incorrect 25 ms 103284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 103284 KB Output is correct
2 Correct 193 ms 111108 KB Output is correct
3 Incorrect 242 ms 106532 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 103284 KB Output is correct
2 Correct 9 ms 103284 KB Output is correct
3 Incorrect 14 ms 103284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 103284 KB Output is correct
2 Correct 12 ms 103284 KB Output is correct
3 Incorrect 16 ms 103284 KB Output isn't correct
4 Halted 0 ms 0 KB -