Submission #838525

#	Time	Username	Problem	Language	Result	Execution time	Memory
838525		sadsa	Wall (IOI14_wall)	C++17	0 / 100	234 ms	63160 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 incr_mi = -1;
    int decr_ma = -1;
    int lazy_last = -1; // 0=incr_mi, 1=decr_ma

    void reset()  {
        incr_mi = -1;
        decr_ma = -1;
    }

    void set_incr_mi(int v) {
        if (incr_mi == -1 || v > incr_mi) {
            lazy_last = 0;    
            incr_mi = v;
            if (decr_ma != -1 && incr_mi >= decr_ma) {
                decr_ma = v;
            }
        }
    }

    void set_decr_ma(int v) {
        if (decr_ma == -1 || v < decr_ma) {
            lazy_last = 1;    
            decr_ma = v;
            if (incr_mi != -1 && decr_ma <= incr_mi) {
                incr_mi = v;
            }
        }
    }

    void cpy(const Node &parent) {
        if (parent.lazy_last == 0) {
            if (parent.decr_ma != -1) set_decr_ma(parent.decr_ma);
            if (parent.incr_mi != -1) set_incr_mi(parent.incr_mi);
        } else {
            if (parent.incr_mi != -1) set_incr_mi(parent.incr_mi);
            if (parent.decr_ma != -1) set_decr_ma(parent.decr_ma);
        }
    }

    int leaf_value() {
        if (lazy_last == -1) return 0;
        return lazy_last? decr_ma: incr_mi;
    }
};

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

    void prop(int p) {
        if (seg[p].incr_mi != -1) DBG("PROP INCR MIN", p, seg[p].incr_mi);
        if (seg[p].decr_ma != -1) DBG("PROP DECR MAX", p, seg[p].decr_ma);

        if (p < N) {
            seg[p*2].cpy(seg[p]);
            seg[p*2+1].cpy(seg[p]);
            //seg[p].reset();
        }
    }

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

        DBG(l, r, vl, vr, p, incr_mi, decr_ma);
        if (l <= vl && vr <= r) {
            if (decr_ma != -1) seg[p].set_decr_ma(decr_ma);
            if (incr_mi != -1) seg[p].set_incr_mi(incr_mi);
            DBG("endnode");
            return;
        }

        int mid = (vl+vr)/2;

        update(l, r, incr_mi, decr_ma, vl, mid, p*2);
        update(l, r, incr_mi, decr_ma, 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);
        }
    }
};

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].leaf_value();
        
}

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