Submission #405512

#	Time	Username	Problem	Language	Result	Execution time	Memory
405512		rocks03	벽 (IOI14_wall)	C++14	100 / 100	806 ms	130712 KiB

wall

#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 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39