oj.uz

Submission #588252

# Submission time Handle Problem Language Result Execution time Memory
588252 2022-07-02T21:44:06 Z AlperenT Wall (IOI14_wall) C++17
100 / 100
 621 ms 91600 KB 
#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

const int N = 2e6 + 5;

int n;

struct SegTree{
    int mn[N * 4], mx[N * 4];

    SegTree(){
        memset(mn, -1, sizeof(mn));
        memset(mx, -1, sizeof(mx));
    }

    void push(int v){
        if(mn[v] != -1){
            if(v * 2 < N * 4){
                if(mn[v * 2] == -1) mn[v * 2] = mn[v];
                else mn[v * 2] = max(mn[v * 2], mn[v]);

                if(mx[v * 2] != -1) mx[v * 2] = max(mx[v * 2], mn[v]);

                if(mn[v * 2 + 1] == -1) mn[v * 2 + 1] = mn[v];
                else mn[v * 2 + 1] = max(mn[v * 2 + 1], mn[v]);

                if(mx[v * 2 + 1] != -1) mx[v * 2 + 1] = max(mx[v * 2 + 1], mn[v]);
            }

            mn[v] = -1;
        }

        if(mx[v] != -1){
            if(v * 2 < N * 4){
                if(mx[v * 2] == -1) mx[v * 2] = mx[v];
                else mx[v * 2] = min(mx[v * 2], mx[v]);

                if(mn[v * 2] != -1) mn[v * 2] = min(mn[v * 2], mx[v]);

                if(mx[v * 2 + 1] == -1) mx[v * 2 + 1] = mx[v];
                else mx[v * 2 + 1] = min(mx[v * 2 + 1], mx[v]);

                if(mn[v * 2 + 1] != -1) mn[v * 2 + 1] = min(mn[v * 2 + 1], mx[v]);
            }

            mx[v] = -1;
        }
    }

    void updatemin(int l, int r, int val, int v = 1, int tl = 0, int tr = n - 1){
        if(l > r) return;
        else if(l == tl && r == tr){
            if(mn[v] == -1) mn[v] = val;
            else{
                mn[v] = max(mn[v], val);
            }

            if(mx[v] != -1) mx[v] = max(mx[v], val);
        }
        else{
            push(v);

            int tm = tl + (tr - tl) / 2;

            updatemin(l, min(tm, r), val, v * 2, tl, tm);
            updatemin(max(tm + 1, l), r, val, v * 2 + 1, tm + 1, tr);
        }
    }

    void updatemax(int l, int r, int val, int v = 1, int tl = 0, int tr = n - 1){
        if(l > r) return;
        else if(l == tl && r == tr){
            if(mx[v] == -1) mx[v] = val;
            else{
                mx[v] = min(mx[v], val);
            }

            if(mn[v] != -1) mn[v] = min(mn[v], val);
        }
        else{
            push(v);

            int tm = tl + (tr - tl) / 2;

            updatemax(l, min(tm, r), val, v * 2, tl, tm);
            updatemax(max(tm + 1, l), r, val, v * 2 + 1, tm + 1, tr);
        }
    }

    void findarr(int *arr, int v = 1, int l = 0, int r = n - 1){
        if(l == r) arr[l] = max(mn[v], 0);
        else{
            push(v);

            int m = l + (r - l) / 2;

            findarr(arr, v * 2, l, m);
            findarr(arr, v * 2 + 1, m + 1, r);
        }
    }
};

SegTree sgt;

void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    n = N;

    for(int i = 0; i < k; i++){
        if(op[i] == 1) sgt.updatemin(left[i], right[i], height[i]);
        else if(op[i] == 2) sgt.updatemax(left[i], right[i], height[i]);
    }

    sgt.findarr(finalHeight);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 62804 KB Output is correct
2 Correct 24 ms 62924 KB Output is correct
3 Correct 26 ms 62924 KB Output is correct
4 Correct 30 ms 63188 KB Output is correct
5 Correct 27 ms 63152 KB Output is correct
6 Correct 31 ms 63116 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 62804 KB Output is correct
2 Correct 163 ms 73684 KB Output is correct
3 Correct 188 ms 68784 KB Output is correct
4 Correct 523 ms 75016 KB Output is correct
5 Correct 277 ms 74856 KB Output is correct
6 Correct 236 ms 75136 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 62864 KB Output is correct
2 Correct 30 ms 63060 KB Output is correct
3 Correct 25 ms 62924 KB Output is correct
4 Correct 36 ms 63068 KB Output is correct
5 Correct 29 ms 63132 KB Output is correct
6 Correct 27 ms 63108 KB Output is correct
7 Correct 23 ms 62804 KB Output is correct
8 Correct 149 ms 73448 KB Output is correct
9 Correct 211 ms 67772 KB Output is correct
10 Correct 506 ms 75064 KB Output is correct
11 Correct 245 ms 75268 KB Output is correct
12 Correct 237 ms 75256 KB Output is correct
13 Correct 24 ms 62804 KB Output is correct
14 Correct 155 ms 73416 KB Output is correct
15 Correct 57 ms 64092 KB Output is correct
16 Correct 621 ms 74532 KB Output is correct
17 Correct 243 ms 74380 KB Output is correct
18 Correct 249 ms 74344 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 62804 KB Output is correct
2 Correct 25 ms 63056 KB Output is correct
3 Correct 25 ms 62976 KB Output is correct
4 Correct 30 ms 63064 KB Output is correct
5 Correct 32 ms 63072 KB Output is correct
6 Correct 27 ms 63060 KB Output is correct
7 Correct 23 ms 62804 KB Output is correct
8 Correct 157 ms 73684 KB Output is correct
9 Correct 188 ms 67788 KB Output is correct
10 Correct 492 ms 74964 KB Output is correct
11 Correct 230 ms 75468 KB Output is correct
12 Correct 237 ms 75620 KB Output is correct
13 Correct 24 ms 62836 KB Output is correct
14 Correct 154 ms 73516 KB Output is correct
15 Correct 64 ms 64108 KB Output is correct
16 Correct 606 ms 74336 KB Output is correct
17 Correct 244 ms 74344 KB Output is correct
18 Correct 235 ms 74356 KB Output is correct
19 Correct 547 ms 91600 KB Output is correct
20 Correct 555 ms 88040 KB Output is correct
21 Correct 534 ms 90544 KB Output is correct
22 Correct 553 ms 88156 KB Output is correct
23 Correct 541 ms 88000 KB Output is correct
24 Correct 537 ms 87908 KB Output is correct
25 Correct 534 ms 87896 KB Output is correct
26 Correct 545 ms 90344 KB Output is correct
27 Correct 546 ms 90216 KB Output is correct
28 Correct 546 ms 87592 KB Output is correct
29 Correct 539 ms 87728 KB Output is correct
30 Correct 541 ms 87868 KB Output is correct