oj.uz

Submission #931078

# Submission time Handle Problem Language Result Execution time Memory
931078 2024-02-21T07:56:40 Z Art_ogo Wall (IOI14_wall) C++17
61 / 100
 375 ms 31060 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] = 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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 6 ms 2908 KB Output is correct
5 Correct 4 ms 2904 KB Output is correct
6 Correct 6 ms 2908 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 103 ms 10296 KB Output is correct
3 Correct 114 ms 6228 KB Output is correct
4 Correct 321 ms 22664 KB Output is correct
5 Correct 206 ms 23432 KB Output is correct
6 Correct 193 ms 21908 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 5 ms 2908 KB Output is correct
5 Correct 5 ms 2908 KB Output is correct
6 Correct 4 ms 2740 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 101 ms 15884 KB Output is correct
9 Correct 118 ms 9912 KB Output is correct
10 Correct 333 ms 22600 KB Output is correct
11 Correct 211 ms 23712 KB Output is correct
12 Correct 193 ms 21904 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 103 ms 15912 KB Output is correct
15 Correct 24 ms 3928 KB Output is correct
16 Correct 375 ms 22612 KB Output is correct
17 Correct 196 ms 22084 KB Output is correct
18 Correct 196 ms 22084 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 5 ms 2908 KB Output is correct
5 Correct 5 ms 2904 KB Output is correct
6 Correct 4 ms 3160 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 101 ms 15956 KB Output is correct
9 Correct 125 ms 9848 KB Output is correct
10 Correct 334 ms 22608 KB Output is correct
11 Correct 198 ms 23452 KB Output is correct
12 Correct 195 ms 21720 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 103 ms 16120 KB Output is correct
15 Correct 22 ms 3928 KB Output is correct
16 Correct 371 ms 22660 KB Output is correct
17 Correct 204 ms 21964 KB Output is correct
18 Correct 196 ms 22096 KB Output is correct
19 Runtime error 123 ms 31060 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -