oj.uz

Submission #405512

# Submission time Handle Problem Language Result Execution time Memory
405512 2021-05-16T13:42:31 Z rocks03 Wall (IOI14_wall) C++14
100 / 100
 806 ms 130712 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << " "
#define nl cout << "\n"
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Node{
    int mn = 0, mx = INT_MAX;
    int lazy = -1;
};

int *ans;
class SegmentTree{
public:
    vector<Node> st;
    void build(int n){
        st = vector<Node>(4 * n);
    }
    void push(int i){
        int cl = 2 * i + 1, cr = 2 * i + 2;
        if(st[i].lazy == 0){
            st[cl].mn = max(st[cl].mn, st[i].mn);
            st[cl].mx = max(st[cl].mx, st[i].mn);
            st[cl].mn = min(st[cl].mn, st[i].mx);
            st[cl].mx = min(st[cl].mx, st[i].mx);
            st[cl].lazy = st[i].lazy;

            st[cr].mn = max(st[cr].mn, st[i].mn);
            st[cr].mx = max(st[cr].mx, st[i].mn);
            st[cr].mn = min(st[cr].mn, st[i].mx);
            st[cr].mx = min(st[cr].mx, st[i].mx);
            st[cr].lazy = st[i].lazy;

        }
        st[i].mn = 0, st[i].mx = INT_MAX, st[i].lazy = -1;
    }
    void add(int i, int l, int r, int ql, int qr, int op, int k){
        if(ql <= l && r <= qr){
            if(op == 0){
                st[i].mn = max(st[i].mn, k);
                st[i].mx = max(st[i].mx, k);
            } else if(op == 1){
                st[i].mn = min(st[i].mn, k);
                st[i].mx = min(st[i].mx, k);
            }
            st[i].lazy = 0;
            return;
        }
        if(qr < l || ql > r){
            return;
        }
        push(i);
        int m = (l + r) / 2;
        add(2 * i + 1, l, m, ql, qr, op, k);
        add(2 * i + 2, m + 1, r, ql, qr, op, k);
    }
    void dfs(int i, int l, int r){
        if(l == r) ans[l] = st[i].mn;
        else{
            push(i);
            int m = (l + r) / 2;
            dfs(2 * i + 1, l, m);
            dfs(2 * i + 2, m + 1, r);
        }
    }
} st;

void buildWall(int N, int K, int op[], int left[], int right[], int height[], int ans[]){
    st.build(N);
    rep(i, 0, K){
        --op[i]; st.add(0, 0, N - 1, left[i], right[i], op[i], height[i]);
    }
    ::ans = ans;
    st.dfs(0, 0, N - 1);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 436 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 972 KB Output is correct
5 Correct 6 ms 972 KB Output is correct
6 Correct 6 ms 972 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 177 ms 13848 KB Output is correct
3 Correct 203 ms 8240 KB Output is correct
4 Correct 587 ms 23048 KB Output is correct
5 Correct 296 ms 24028 KB Output is correct
6 Correct 295 ms 22456 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 328 KB Output is correct
4 Correct 7 ms 944 KB Output is correct
5 Correct 5 ms 1012 KB Output is correct
6 Correct 6 ms 996 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 212 ms 13860 KB Output is correct
9 Correct 202 ms 8260 KB Output is correct
10 Correct 588 ms 22992 KB Output is correct
11 Correct 305 ms 24044 KB Output is correct
12 Correct 292 ms 22468 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 162 ms 13940 KB Output is correct
15 Correct 33 ms 2296 KB Output is correct
16 Correct 595 ms 23220 KB Output is correct
17 Correct 292 ms 22672 KB Output is correct
18 Correct 292 ms 22764 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 436 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 948 KB Output is correct
5 Correct 5 ms 960 KB Output is correct
6 Correct 5 ms 972 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 167 ms 13996 KB Output is correct
9 Correct 211 ms 8204 KB Output is correct
10 Correct 579 ms 23020 KB Output is correct
11 Correct 303 ms 24044 KB Output is correct
12 Correct 293 ms 22468 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 165 ms 13892 KB Output is correct
15 Correct 33 ms 2300 KB Output is correct
16 Correct 603 ms 23224 KB Output is correct
17 Correct 317 ms 22640 KB Output is correct
18 Correct 291 ms 22636 KB Output is correct
19 Correct 725 ms 130568 KB Output is correct
20 Correct 729 ms 128120 KB Output is correct
21 Correct 740 ms 130688 KB Output is correct
22 Correct 712 ms 128088 KB Output is correct
23 Correct 725 ms 128048 KB Output is correct
24 Correct 713 ms 128200 KB Output is correct
25 Correct 722 ms 128168 KB Output is correct
26 Correct 738 ms 130564 KB Output is correct
27 Correct 727 ms 130712 KB Output is correct
28 Correct 741 ms 128068 KB Output is correct
29 Correct 767 ms 128068 KB Output is correct
30 Correct 806 ms 128072 KB Output is correct