제출 #622815

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
622815		yuto1115	벽 (IOI14_wall)	C++17	100 / 100	546 ms	75848 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); ++i)
#define rrep(i, n) for(ll i = ll(n) - 1; i >= 0; --i)
#define rrep2(i, n, t) for(ll i = ll(n) - 1; i >= ll(t); --i)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define SZ(a) int(a.size())
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

using S = P;
const S e = {0, inf};

constexpr S op(const S &l, const S &r) {
    if (l.second <= r.first) return {r.first, r.first};
    if (r.second <= l.first) return {r.second, r.second};
    return {max(l.first, r.first), min(l.second, r.second)};
}

class dual_segtree {
    int n, log;
    vector<S> d;
    
    void all_apply(int p, const S &x) {
        d[p] = op(d[p], x);
    }
    
    void push(int p) {
        all_apply(2 * p, d[p]);
        all_apply(2 * p + 1, d[p]);
        d[p] = e;
    }

public:
    dual_segtree(int _n) {
        log = 1;
        while (1 << log < _n) ++log;
        n = 1 << log;
        d.assign(2 * n, e);
    }
    
    void apply(int l, int r, const S &x) {
        assert(0 <= l and l <= r and r <= n);
        l += n, r += n;
        rrep2(i, log + 1, 1) {
            if (l >> i << i != l) push(l >> i);
            if (r >> i << i != r) push(r >> i);
        }
        while (l < r) {
            if (l & 1) all_apply(l++, x);
            if (r & 1) all_apply(--r, x);
            l >>= 1, r >>= 1;
        }
    }
    
    vector<S> all_get() {
        rep2(i, 1, n) push(i);
        return vector<S>(d.begin() + n, d.end());
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    dual_segtree st(n);
    rep(i, k) {
        ++right[i];
        if (op[i] == 1) st.apply(left[i], right[i], {height[i], inf});
        else st.apply(left[i], right[i], {0, height[i]});
    }
    auto ans = st.all_get();
    rep(i, n) finalHeight[i] = ans[i].first;
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39