Submission #640886

#	Time	Username	Problem	Language	Result	Execution time	Memory
640886		Sharky	Wall (IOI14_wall)	C++17	100 / 100	799 ms	100332 KiB

wall

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

using node = pair<int, int>;
#define mn first
#define mx second
const int inf = 1E9+7;

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

struct segtree {
    int size = 1;
    vector<node> seg, lazy;
    vector<int> ans;
    void init(int N) {
        while (size < N) size *= 2;
        seg.assign(2 * size, {0, 0});
        lazy.assign(2 * size, {0, 0});
        ans.assign(size + 1, 0);
    }
    void add(int id, int x) {
        ckmax(seg[id].mn, x);
        ckmax(seg[id].mx, x);
        ckmax(lazy[id].mn, x);
        ckmax(lazy[id].mx, x);
    }
    void rem(int id, int x) {
        ckmin(seg[id].mn, x);
        ckmin(seg[id].mx, x);
        ckmin(lazy[id].mn, x);
        ckmin(lazy[id].mx, x);
    }
    void push(int id) {
        if (lazy[id].mx != -inf) {
            for (int i = 0; i < 2; i++) {
                add(id * 2 + i, lazy[id].mx);
            }
        }
        if (lazy[id].mn != inf) {
            for (int i = 0; i < 2; i++) {
                rem(id * 2 + i, lazy[id].mn);
            }
        }
        lazy[id] = {inf, -inf};
    }
    node merge(node lhs, node rhs) {
        node rv;
        rv.mn = min(lhs.mn, rhs.mn);
        rv.mx = max(lhs.mx, rhs.mx); 
        return rv;
    }
    void pull(int id) {
        seg[id] = merge(seg[id * 2], seg[id * 2 + 1]);
    }
    void upd(int op, int ql, int qr, int x, int id, int l, int r) {
        if (l > qr || r < ql) return;
        if (ql <= l && r <= qr) {
            if (op == 1) add(id, x);
            else rem(id, x);
            return;
        }
        push(id);
        int mid = (l + r) / 2;
        upd(op, ql, qr, x, id * 2, l, mid);
        upd(op, ql, qr, x, id * 2 + 1, mid + 1, r);
        pull(id);
    }
    void upd(int op, int ql, int qr, int x) {
        upd(op, ql, qr, x, 1, 0, size - 1);
    }
    // node query(int ql, int qr, int id, int l, int r) {
    //     printf("id = %d, l = %d, r = %d\n", id, l, r);
    //     push(id);
    //     if (l > qr || r < ql) return {inf, -inf};
    //     if (ql <= l && r <= qr) return seg[id];
    //     int mid = (l + r) / 2;
    //     node lhs = query(ql, qr, id * 2, l, mid);
    //     node rhs = query(ql, qr, id * 2 + 1, mid + 1, r);
    //     return merge(lhs, rhs);
    // }
    // node query(int ql, int qr) {
    //     return query(ql, qr, 1, 0, size - 1);
    // }
    void calc(int id, int l, int r) {
        if (l == r) ans[l] = seg[id].mn;
        else {
            push(id);
            int mid = (l + r) / 2;
            calc(id * 2, l, mid);
            calc(id * 2 + 1, mid + 1, r);
        }
    }
    void calc() {
        calc(1, 0, size - 1);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    segtree st;
    st.init(n);
    for (int i = 0; i < k; i++) {
        st.upd(op[i], left[i], right[i], height[i]);
    }
    st.calc();
    for (int i = 0; i < n; i++) finalHeight[i] = st.ans[i];
}

#ifndef EVAL

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, q;
    cin >> n >> q;
    segtree st;
    st.init(n);
    while (q--) {
        int op, l, r, h;
        cin >> op >> l >> r >> h;
        st.upd(op, l, r, h);
    }
    st.calc();
    for (int i = 0; i < n; i++) {
        cout << st.ans[i] << "\n";
    }

    return 0;
}

#endif

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