oj.uz

Submission #815709

# Submission time Handle Problem Language Result Execution time Memory
815709 2023-08-08T19:33:10 Z Liudas Wall (IOI14_wall) C++17
100 / 100
 915 ms 59304 KB 
#include <bits/stdc++.h>
#include "wall.h"
#include "wall.h"
using namespace std;
class seg_tree{
public:
    struct node{
        int maxi;
        int mini;
    };
    vector<node> tree;
    int N;
    node em = {0, INT_MAX};
    seg_tree(int K){
        N = 1;
        while(N <= K){
            N *= 2;
        }
        tree.assign(N * 2, em);
    }
    node apply(node a, node b){
        node c = a;
        c.maxi = min(max(a.maxi, b.maxi), b.mini);
        c.mini = min(max(a.mini, b.maxi), b.mini);
        return c;
    }
    void propogate(int head, int L, int R){
        if(R - L == 1)return;
        tree[head * 2 + 1] = apply(tree[head * 2 + 1], tree[head]);
        tree[head * 2 + 2] = apply(tree[head * 2 + 2], tree[head]);
        tree[head] = em;
    }
    void mod(int head, int l, int r, int L, int R, int v1, int v2){
        propogate(head, L, R);
        if(l <= L && R <= r){
            if(v2){
                tree[head].maxi = max(tree[head].maxi, v1);
                tree[head].mini = max(tree[head].mini, v1);
            }
            else{
                tree[head].mini = min(tree[head].mini, v1);
                tree[head].maxi = min(tree[head].maxi, v1);
            }
            return;
        }
        if(R <= l || L >= r){
            return;
        }
        int mid = (L + R) / 2;
        mod(head * 2 + 1, l, r, L, mid, v1, v2);
        mod(head * 2 + 2, l, r, mid, R, v1, v2);
    }
    void mod(int v1, int v2, int l, int r){
        mod(0, l, r, 0, N, v1, v2);
    }
    int get(int head, int L, int R, int pos){
        propogate(head, L, R);
        if(R-L == 1){
            return min(tree[head].maxi, tree[head].mini);
        }
        int mid = (L + R) / 2;
        int ans;
        if(pos < mid){
            ans = get(head * 2 + 1, L, mid, pos);
        }
        else{
            ans = get(head * 2 + 2, mid, R, pos);
        }
        return ans;
    }
    int get(int pos){
        return get(0, 0, N, pos);
    }
};
void buildWall(int N, int K, int op[], int l[], int r[], int h[], int fh[]){
    seg_tree tree(N);
    for(int i = 0; i < K; i ++){
        int OP = op[i], L = l[i], R = r[i], H = h[i];
        if(OP == 1){
            tree.mod(H, 1, L, R + 1);
        }
        else{
            tree.mod(H, 0, L, R + 1);
        }
    }
    for(int i = 0; i < N; i ++){
        fh[i] = tree.get(i);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 6 ms 724 KB Output is correct
5 Correct 5 ms 724 KB Output is correct
6 Correct 5 ms 724 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 117 ms 13868 KB Output is correct
3 Correct 142 ms 7884 KB Output is correct
4 Correct 400 ms 20176 KB Output is correct
5 Correct 292 ms 20724 KB Output is correct
6 Correct 254 ms 19036 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 5 ms 724 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 117 ms 13840 KB Output is correct
9 Correct 136 ms 7844 KB Output is correct
10 Correct 390 ms 20172 KB Output is correct
11 Correct 268 ms 20620 KB Output is correct
12 Correct 256 ms 19104 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 145 ms 13868 KB Output is correct
15 Correct 23 ms 1884 KB Output is correct
16 Correct 391 ms 20172 KB Output is correct
17 Correct 264 ms 19532 KB Output is correct
18 Correct 280 ms 19564 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 5 ms 724 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 0 ms 276 KB Output is correct
8 Correct 116 ms 13932 KB Output is correct
9 Correct 143 ms 7904 KB Output is correct
10 Correct 396 ms 20172 KB Output is correct
11 Correct 260 ms 20712 KB Output is correct
12 Correct 260 ms 19160 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 122 ms 13936 KB Output is correct
15 Correct 24 ms 1892 KB Output is correct
16 Correct 396 ms 20232 KB Output is correct
17 Correct 297 ms 19480 KB Output is correct
18 Correct 264 ms 19596 KB Output is correct
19 Correct 842 ms 59116 KB Output is correct
20 Correct 824 ms 59180 KB Output is correct
21 Correct 853 ms 59164 KB Output is correct
22 Correct 812 ms 59092 KB Output is correct
23 Correct 835 ms 59164 KB Output is correct
24 Correct 855 ms 59160 KB Output is correct
25 Correct 830 ms 59188 KB Output is correct
26 Correct 843 ms 59208 KB Output is correct
27 Correct 835 ms 59204 KB Output is correct
28 Correct 915 ms 59204 KB Output is correct
29 Correct 830 ms 59212 KB Output is correct
30 Correct 899 ms 59304 KB Output is correct