Submission #700311

#	Time	Username	Problem	Language	Result	Execution time	Memory
700311		Forested	Wall (IOI14_wall)	C++17	100 / 100	738 ms	48784 KiB

wall

#include "wall.h"

#include <bits/stdc++.h>
using namespace std;

using i32 = int;
using i64 = long long;
template <typename T>
using Vec = vector<T>;

#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define ALL(x) begin(x), end(x)
#define PER(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)

template <typename T>
bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    } else {
        return false;
    }
}
template <typename T>
bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    } else {
        return false;
    }
}

constexpr i32 INF = 1001001001;
constexpr i64 INF64 = 3003003003003003003;

i32 ceil_pow2(i32 n) {
    i32 k = 1;
    while (k < n) {
        k *= 2;
    }
    return k;
}

struct Func {
    i32 lo, hi;
};

Func id() {
    return Func{-INF, INF};
}
Func composite(Func f, Func g) {
    if (f.lo > g.hi) {
        return Func{f.lo, f.lo};
    }
    if (f.hi < g.lo) {
        return Func{f.hi, f.hi};
    }
    return Func{max(f.lo, g.lo), min(f.hi, g.hi)};
}

class DualSegmentTree {
    i32 n;
    Vec<Func> funcs;
    
    void push(i32 idx) {
        if (idx < n) {
            funcs[2 * idx] = composite(funcs[idx], funcs[2 * idx]);
            funcs[2 * idx + 1] = composite(funcs[idx], funcs[2 * idx + 1]);
            funcs[idx] = id();
        }
    }
    
    void _apply(i32 l, i32 r, Func f, i32 cur, i32 curl, i32 curr) {
        if (curr <= l || r <= curl) {
            return;
        }
        if (l <= curl && curr <= r) {
            funcs[cur] = composite(f, funcs[cur]);
            return;
        }
        i32 curm = (curl + curr) / 2;
        push(cur);
        _apply(l, r, f, 2 * cur, curl, curm);
        _apply(l, r, f, 2 * cur + 1, curm, curr);
    }
    
public:
    DualSegmentTree(i32 n_) : n(ceil_pow2(n_)), funcs(2 * n, id()) {}
    
    void apply(i32 l, i32 r, Func f) {
        _apply(l, r, f, 1, 0, n);
    }
    
    Func get(i32 idx) const {
        idx += n;
        Func ret = id();
        while (idx > 0) {
            ret = composite(funcs[idx], ret);
            idx /= 2;
        }
        return ret;
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    DualSegmentTree seg(n);
    REP(i, k) {
        if (op[i] == 1) {
            seg.apply(left[i], right[i] + 1, Func{height[i], INF});
        } else {
            seg.apply(left[i], right[i] + 1, Func{-INF, height[i]});
        }
    }
    REP(i, n) {
        Func f = seg.get(i);
        finalHeight[i] = (0 < f.lo ? f.lo : 0 > f.hi ? f.hi : 0);
    }
}

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