oj.uz

Submission #1041898

# Submission time Handle Problem Language Result Execution time Memory
1041898 2024-08-02T09:38:26 Z BF001 Wall (IOI14_wall) C++17
100 / 100
 434 ms 170072 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define N 2000005
#define oo (1e9 + 1)

int n, k, res[N], q;

struct node{
    int ma, mi, lma, lmi;
    node(){
        ma = mi = 0;
        lma = -oo; lmi = oo;
    }
};

vector<node> bit;

void add(int id, int ma){
    bit[id].mi = max(bit[id].mi, ma);
    bit[id].ma = max(bit[id].ma, ma);
    bit[id].lmi = max(bit[id].lmi, ma);
    bit[id].lma = max(bit[id].lma, ma);
}

void dec(int id, int mi){
    bit[id].mi = min(bit[id].mi, mi);
    bit[id].ma = min(bit[id].ma, mi);
    bit[id].lmi = min(bit[id].lmi, mi);
    bit[id].lma = min(bit[id].lma, mi);
}

void down(int id, int l, int r){
    if (l == r) return;
    if (bit[id].lmi != oo){
        dec(id * 2, bit[id].lmi);
        dec(id * 2 + 1, bit[id].lmi);
    }
    if (bit[id].lma != -oo){
        add(id * 2, bit[id].lma);
        add(id * 2 + 1, bit[id].lma);
    }
    bit[id].lmi = oo;
    bit[id].lma = -oo;
}

void ud(int id, int l, int r, int u, int v, int t, int val){
    if (l > v || r < u) return;
    if (l >= u && r <= v){
        if (t != 1) dec(id, val);
        else add(id, val);
        return;
    }
    int mid = (l + r) >> 1;
    down(id, l, r);
    ud(id * 2, l, mid, u, v, t, val);
    ud(id * 2 + 1, mid + 1, r, u, v, t, val);
    bit[id].mi = min(bit[id * 2].mi, bit[id * 2 + 1].mi);
    bit[id].ma = max(bit[id * 2].ma, bit[id * 2 + 1].ma);
}

void go(int id, int l, int r){
    if (l == r){
        res[l] = bit[id].mi;
        return;
    }
    down(id, l, r);
    int mid = (l + r) >> 1;
    go(id * 2, l, mid);
    go(id * 2 + 1, mid + 1, r);
}

 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    bit.resize(4 * n + 1);
    for (int i = 0; i < k; i++){
        ud(1, 1, n, left[i] + 1, right[i] + 1, op[i], height[i]);
    }
    go(1, 1, n);
    for (int i = 1; i <= n; i++) finalHeight[i - 1] = res[i];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 1372 KB Output is correct
5 Correct 5 ms 1236 KB Output is correct
6 Correct 5 ms 1160 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 79 ms 14004 KB Output is correct
3 Correct 158 ms 8708 KB Output is correct
4 Correct 399 ms 26716 KB Output is correct
5 Correct 220 ms 27880 KB Output is correct
6 Correct 163 ms 26300 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1372 KB Output is correct
5 Correct 5 ms 1284 KB Output is correct
6 Correct 3 ms 1372 KB Output is correct
7 Correct 0 ms 444 KB Output is correct
8 Correct 70 ms 13908 KB Output is correct
9 Correct 154 ms 8784 KB Output is correct
10 Correct 344 ms 26708 KB Output is correct
11 Correct 228 ms 27984 KB Output is correct
12 Correct 189 ms 26192 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 78 ms 13956 KB Output is correct
15 Correct 19 ms 2644 KB Output is correct
16 Correct 420 ms 27040 KB Output is correct
17 Correct 190 ms 26460 KB Output is correct
18 Correct 174 ms 26488 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 452 KB Output is correct
4 Correct 4 ms 1372 KB Output is correct
5 Correct 3 ms 1372 KB Output is correct
6 Correct 3 ms 1368 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 68 ms 13868 KB Output is correct
9 Correct 127 ms 8784 KB Output is correct
10 Correct 379 ms 26812 KB Output is correct
11 Correct 178 ms 27984 KB Output is correct
12 Correct 225 ms 26348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 114 ms 13992 KB Output is correct
15 Correct 23 ms 2648 KB Output is correct
16 Correct 372 ms 27020 KB Output is correct
17 Correct 172 ms 26536 KB Output is correct
18 Correct 181 ms 26452 KB Output is correct
19 Correct 434 ms 169812 KB Output is correct
20 Correct 424 ms 167252 KB Output is correct
21 Correct 407 ms 170068 KB Output is correct
22 Correct 397 ms 167204 KB Output is correct
23 Correct 408 ms 167288 KB Output is correct
24 Correct 395 ms 167248 KB Output is correct
25 Correct 403 ms 167284 KB Output is correct
26 Correct 410 ms 169812 KB Output is correct
27 Correct 408 ms 170072 KB Output is correct
28 Correct 412 ms 167252 KB Output is correct
29 Correct 397 ms 167252 KB Output is correct
30 Correct 400 ms 167248 KB Output is correct