oj.uz

Submission #697824

# Submission time Handle Problem Language Result Execution time Memory
697824 2023-02-11T07:00:52 Z Elvin_Fritl Wall (IOI14_wall) C++17
100 / 100
 940 ms 130712 KB 
#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
using ll = long long;
const int N = 2e6 + 5;
const int inf = 1e9 + 7;
 
struct Node {
    int sum;
    int mx = inf;
    int mn = 0;
} 
st[N * 4];
 
void push (int x) {
    st[x * 2].mn = min(st[x].mx, max(st[x].mn, st[x * 2].mn));
    st[x * 2].mx = max(st[x].mn, min(st[x].mx, st[x * 2].mx));
    st[x * 2 + 1].mn = min(st[x].mx, max(st[x].mn, st[x * 2 + 1].mn));
    st[x * 2 + 1].mx = max(st[x].mn, min(st[x].mx, st[x * 2 + 1].mx));
    st[x].mn = 0;
    st[x].mx = inf;
}
 
void update (int l, int r, int h, int op, int x = 1, int L = 1, int R = N - 1) {
    if (L > r || R < l) return;
    if (l <= L && R <= r) {
        if (op == 1) {
            st[x].mn = max(st[x].mn, h);
            st[x].mx = max(st[x].mx, h);    
        }
        else {
            st[x].mn = min(st[x].mn, h);
            st[x].mx = min(st[x].mx, h);    
        }
    }
    else {
        push(x);
        int M = (L + R) / 2;
        update(l, r, h, op, x * 2, L, M);
        update(l, r, h, op, x * 2 + 1, M + 1, R);
    }
}
 
int get (int pos, int x = 1, int L = 1, int R = N - 1) {
    if (L == R) 
        return st[x].mn;
    push(x);
    int M = (L + R) / 2;
    if (pos <= M) 
        return get(pos, x * 2, L, M);
    
    return get(pos, x * 2 + 1, M + 1, R);    
}
 
void buildWall (int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    for (int i = 0; i < k; i++) {
        update(left[i] + 1, right[i] + 1, height[i], op[i]);
    }
    for (int i = 1; i <= n; i++) {
        finalHeight[i - 1] = get(i);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94100 KB Output is correct
2 Correct 40 ms 94260 KB Output is correct
3 Correct 38 ms 94200 KB Output is correct
4 Correct 50 ms 94308 KB Output is correct
5 Correct 48 ms 94304 KB Output is correct
6 Correct 48 ms 94360 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 94160 KB Output is correct
2 Correct 279 ms 102060 KB Output is correct
3 Correct 199 ms 97556 KB Output is correct
4 Correct 471 ms 102580 KB Output is correct
5 Correct 327 ms 113248 KB Output is correct
6 Correct 328 ms 111688 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 94164 KB Output is correct
2 Correct 41 ms 94244 KB Output is correct
3 Correct 46 ms 94228 KB Output is correct
4 Correct 44 ms 94276 KB Output is correct
5 Correct 44 ms 94344 KB Output is correct
6 Correct 43 ms 94300 KB Output is correct
7 Correct 39 ms 94252 KB Output is correct
8 Correct 258 ms 102036 KB Output is correct
9 Correct 197 ms 97548 KB Output is correct
10 Correct 453 ms 102644 KB Output is correct
11 Correct 358 ms 113248 KB Output is correct
12 Correct 329 ms 111700 KB Output is correct
13 Correct 39 ms 94108 KB Output is correct
14 Correct 266 ms 107808 KB Output is correct
15 Correct 64 ms 95360 KB Output is correct
16 Correct 468 ms 112404 KB Output is correct
17 Correct 323 ms 111912 KB Output is correct
18 Correct 327 ms 111992 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 94168 KB Output is correct
2 Correct 44 ms 94212 KB Output is correct
3 Correct 41 ms 94176 KB Output is correct
4 Correct 44 ms 94284 KB Output is correct
5 Correct 44 ms 94328 KB Output is correct
6 Correct 44 ms 94260 KB Output is correct
7 Correct 39 ms 94212 KB Output is correct
8 Correct 271 ms 101960 KB Output is correct
9 Correct 196 ms 97528 KB Output is correct
10 Correct 466 ms 102652 KB Output is correct
11 Correct 326 ms 113248 KB Output is correct
12 Correct 312 ms 111788 KB Output is correct
13 Correct 39 ms 94228 KB Output is correct
14 Correct 273 ms 107816 KB Output is correct
15 Correct 66 ms 95408 KB Output is correct
16 Correct 481 ms 112520 KB Output is correct
17 Correct 329 ms 111952 KB Output is correct
18 Correct 312 ms 112020 KB Output is correct
19 Correct 923 ms 130604 KB Output is correct
20 Correct 923 ms 128112 KB Output is correct
21 Correct 897 ms 130544 KB Output is correct
22 Correct 884 ms 128032 KB Output is correct
23 Correct 892 ms 128248 KB Output is correct
24 Correct 892 ms 128076 KB Output is correct
25 Correct 894 ms 128072 KB Output is correct
26 Correct 927 ms 130712 KB Output is correct
27 Correct 922 ms 130516 KB Output is correct
28 Correct 905 ms 128008 KB Output is correct
29 Correct 901 ms 128128 KB Output is correct
30 Correct 940 ms 128124 KB Output is correct