Submission #834883

#	Time	Username	Problem	Language	Result	Execution time	Memory
834883		sadsa	Wall (IOI14_wall)	C++17	24 / 100	774 ms	74188 KiB

wall

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

using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;

using i64 = int64_t;
using vl = vector<i64>;
using ll = pair<i64, i64>;
using vll = vector<ll>;

constexpr int iINF = numeric_limits<int>::max();
constexpr i64 lINF = numeric_limits<i64>::max();

#define RANGE(x) begin(x), end(x)

template <typename... T>
void DBG(T&&... args) {
    //((cerr << args << ' '), ...) << '\n';
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &vec) {
    out << '{';
    for (size_t i = 0; i < vec.size()-1; ++i)
        out << vec[i] << ", ";
    out << vec.back() << '}';
    return out;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &pr) {
    out << '(' << pr.first << ", " << pr.second << ')';
    return out;
}

struct Node {
    int mi{}, ma{};
    int ladd = -1;
    int lrem = -1;

    void cpy(const Node &n) {
        if (ladd == -1) ladd = n.ladd;
        else if (n.ladd != -1) ladd = max(ladd, n.ladd);

        if (lrem == -1) lrem = n.lrem;
        else if (n.lrem != -1) lrem = min(lrem, n.lrem);
    }

    void prop() {
        if (ladd!=-1) {
            if (ladd > mi) mi = ladd;
            if (ladd > ma) ma = ladd;
        }

        if (lrem!=-1) {
            if (lrem < ma) ma = lrem;
            if (lrem < mi) mi = lrem;
        }

        tie(mi, ma) = minmax(mi, ma);
    }

    void reset() {
        ladd = -1;
        lrem = -1;
    }
};

static constexpr int N = 1 << 21;
struct Seg {
    vector<Node> seg = vector<Node>(N * 2);

    void prop(int p) {
        seg[p].prop();
        if (p < N) {
            seg[p*2].cpy(seg[p]);
            seg[p*2+1].cpy(seg[p]);
        }
        if (seg[p].ladd != -1) DBG("PROP ADD", p, seg[p].ladd);
        if (seg[p].lrem != -1) DBG("PROP REM", p, seg[p].lrem);
        seg[p].reset();
    }

    void update(int l, int r, int ladd, int lrem, int vl=0, int vr=N-1, int p=1) {
        prop(p);
        if (l > vr || r < vl) return;

        DBG(l, r, vl, vr, p, ladd, lrem);
        if (l <= vl && vr <= r) {
            seg[p].lrem = lrem;
            seg[p].ladd = ladd;
            DBG("endnode");
            return;
        }

        int mid = (vl+vr)/2;

        update(l, r, ladd, lrem, vl, mid, p*2);
        update(l, r, ladd, lrem, mid+1, vr, p*2+1);
    }

    void prop_rec(int p=1) {
        prop(p);

        if (p < N) {
            prop_rec(p*2);
            prop_rec(p*2+1);
        } else {
            prop(p);
        }
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    Seg seg;
    seg.prop_rec();
    DBG("START");

    for (int i = 0; i < k; ++i) {
        DBG("-----------UPDATE", i);
        seg.update(left[i], right[i], op[i] == 1? height[i]: -1, op[i] == 2? height[i]: -1);
    }

    DBG("DONE");
    seg.prop_rec();
    for (int i = 0; i < n; ++i)
        finalHeight[i] = seg.seg[i + N].mi;
        
}

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