oj.uz

Submission #681668

# Submission time Handle Problem Language Result Execution time Memory
681668 2023-01-13T15:52:56 Z kusssso Wall (IOI14_wall) C++17
100 / 100
 902 ms 130676 KB 
#include<bits/stdc++.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[]) {
    // cout << st[0].mx << ' '<<st[0].mn << '\n';
    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);
        // cout << get(i) << ' ';
    }
}

// signed main() {
    // ios_base::sync_with_stdio(0);
    // cin.tie(0);
//     
    // int op[] = {1, 2, 2, 1, 1, 2};
    // int left[] = {1, 4, 3, 0, 2, 6};
    // int right[] = {8, 9, 6, 5, 2, 7};
    // int height[] = {4, 1, 5, 3, 5, 0};
    // int finalHeight[10];
    // buildWall(10, 6, op, left, right, height, finalHeight);
//     
    // return 0;
// }

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 94156 KB Output is correct
2 Correct 41 ms 94320 KB Output is correct
3 Correct 41 ms 94228 KB Output is correct
4 Correct 46 ms 94476 KB Output is correct
5 Correct 50 ms 94412 KB Output is correct
6 Correct 44 ms 94412 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 94228 KB Output is correct
2 Correct 301 ms 107864 KB Output is correct
3 Correct 198 ms 101332 KB Output is correct
4 Correct 456 ms 112224 KB Output is correct
5 Correct 330 ms 113260 KB Output is correct
6 Correct 332 ms 111620 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 94208 KB Output is correct
2 Correct 41 ms 94236 KB Output is correct
3 Correct 42 ms 94164 KB Output is correct
4 Correct 47 ms 94356 KB Output is correct
5 Correct 55 ms 94404 KB Output is correct
6 Correct 44 ms 94412 KB Output is correct
7 Correct 43 ms 94212 KB Output is correct
8 Correct 263 ms 107772 KB Output is correct
9 Correct 204 ms 101324 KB Output is correct
10 Correct 489 ms 112208 KB Output is correct
11 Correct 342 ms 113288 KB Output is correct
12 Correct 326 ms 111696 KB Output is correct
13 Correct 41 ms 94100 KB Output is correct
14 Correct 282 ms 107800 KB Output is correct
15 Correct 66 ms 95384 KB Output is correct
16 Correct 457 ms 112404 KB Output is correct
17 Correct 324 ms 112044 KB Output is correct
18 Correct 311 ms 111856 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 94164 KB Output is correct
2 Correct 41 ms 94264 KB Output is correct
3 Correct 40 ms 94280 KB Output is correct
4 Correct 45 ms 94404 KB Output is correct
5 Correct 44 ms 94412 KB Output is correct
6 Correct 43 ms 94440 KB Output is correct
7 Correct 38 ms 94164 KB Output is correct
8 Correct 265 ms 107904 KB Output is correct
9 Correct 192 ms 101364 KB Output is correct
10 Correct 452 ms 112216 KB Output is correct
11 Correct 330 ms 113308 KB Output is correct
12 Correct 309 ms 111684 KB Output is correct
13 Correct 40 ms 94156 KB Output is correct
14 Correct 284 ms 107800 KB Output is correct
15 Correct 70 ms 95328 KB Output is correct
16 Correct 464 ms 112436 KB Output is correct
17 Correct 310 ms 111948 KB Output is correct
18 Correct 318 ms 112020 KB Output is correct
19 Correct 882 ms 130512 KB Output is correct
20 Correct 877 ms 128044 KB Output is correct
21 Correct 892 ms 130676 KB Output is correct
22 Correct 882 ms 128308 KB Output is correct
23 Correct 886 ms 128120 KB Output is correct
24 Correct 887 ms 128204 KB Output is correct
25 Correct 883 ms 128120 KB Output is correct
26 Correct 900 ms 130572 KB Output is correct
27 Correct 902 ms 130624 KB Output is correct
28 Correct 872 ms 127996 KB Output is correct
29 Correct 886 ms 128136 KB Output is correct
30 Correct 886 ms 128088 KB Output is correct