Submission #592889

#	Time	Username	Problem	Language	Result	Execution time	Memory
592889		skittles1412	Wall (IOI14_wall)	C++17	100 / 100	639 ms	113328 KiB

wall

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

struct Node {
    int l, r;

    Node operator+(const Node& n) const {
        if (n.r < l) {
            return {n.r, n.r};
        } else if (r < n.l) {
            return {n.l, n.l};
        }
        return {max(l, n.l), min(r, n.r)};
    }
} ndef {0, int(1e9)};

struct ST {
    int n;
    vector<Node> v;

    ST(int n) : n(n), v(4 * n, ndef) {}

    void set(int o, int l, int r, int ind, const Node& x) {
        if (l == r) {
            v[o] = x;
        } else {
            int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
            if (ind <= mid) {
                set(lc, l, mid, ind, x);
            } else {
                set(rc, mid + 1, r, ind, x);
            }
            v[o] = v[lc] + v[rc];
        }
    }

    void set(int ind, const Node& x) {
        set(1, 0, n - 1, ind, x);
    }

    Node query_all() {
        return v[1];
    }
};

void buildWall(int n,
               int q,
               int op[],
               int ql[],
               int qr[],
               int qx[],
               int out[]) {
    vector<pair<bool, int>> ops[n + 1];
    for (int i = 0; i < q; i++) {
        ops[ql[i]].emplace_back(true, i);
        ops[qr[i] + 1].emplace_back(false, i);
    }
    ST st(q);
    for (int i = 0; i < n; i++) {
        for (auto& [add, j] : ops[i]) {
            if (add) {
                if (op[j] == 1) {
                    st.set(j, {qx[j], int(1e9)});
                } else {
                    st.set(j, {0, qx[j]});
                }
            } else {
                st.set(j, ndef);
            }
        }
        out[i] = st.query_all().l;
    }
}

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