oj.uz

Submission #931073

# Submission time Handle Problem Language Result Execution time Memory
931073 2024-02-21T07:50:34 Z Art_ogo Wall (IOI14_wall) C++17
0 / 100
 101 ms 10136 KB 
#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] = max(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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Incorrect 101 ms 10136 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Incorrect 2 ms 2392 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 2 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -