Submission #1205587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205587		andrejikus	Wall (IOI14_wall)	C++20	100 / 100	591 ms	89168 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
typedef long long ll;
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) { cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...); }
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)

const int N = 2e6 + 3;
const int inf = 1e9;

struct node {
    int opmax, opmin;
};

struct segtree {
    vector<node> op;
    int size_s = 1;
    void init(int n) {
        while (size_s <= n) size_s *= 2;
        op.assign(4*N, {0, inf});
    }

    void propagate(int x, int lx, int rx) {
        if (rx - lx == 1) return;
        op[x*2+1] = {min(op[x].opmin, max(op[x*2+1].opmax, op[x].opmax)), max(op[x].opmax, min(op[x*2+1].opmin, op[x].opmin))};
        op[x*2+2] = {min(op[x].opmin, max(op[x*2+2].opmax, op[x].opmax)), max(op[x].opmax, min(op[x*2+2].opmin, op[x].opmin))};
        op[x] = {0, inf};
    }

    void minimum(int x, int lx, int rx, int l, int r, int v) {
        if (lx >= r || rx <= l) return;
        if (lx >= l && rx <= r) {
            op[x].opmin = min(op[x].opmin, v);
            op[x].opmax = min(op[x].opmax, v);
            return;
        }
        propagate(x, lx, rx);
        int m = (lx + rx) / 2;
        minimum(x * 2 + 1, lx, m, l, r, v);
        minimum(x * 2 + 2, m, rx, l, r, v);
    }

    void minimum(int l, int r, int v) {
        minimum(0, 0, N, l, r+1, v);
    }

    void maksimum(int x, int lx, int rx, int l, int r, int v) {
        //dbg(size_s, lx, rx, l, r);
        if (lx >= r || rx <= l) return;
        if (lx >= l && rx <= r) {
            op[x].opmin = max(op[x].opmin, v);
            op[x].opmax = max(op[x].opmax, v);
            return;
        }
        propagate(x, lx, rx);
        int m = (lx + rx) / 2;
        maksimum(x * 2 + 1, lx, m, l, r, v);
        maksimum(x * 2 + 2, m, rx, l, r, v);
    }

    void maksimum(int l, int r, int v) {
        maksimum(0, 0, N, l, r+1, v);
    }

    int get(int x, int lx, int rx, int i) {
        if (rx - lx == 1)
            return op[x].opmax;
        propagate(x, lx, rx);
        int m = (lx + rx) / 2;
        if (i < m)
            return get(x * 2 + 1, lx, m, i);
        else
            return get(x * 2 + 2, m, rx, i);
    }

    int get(int i) {
        return get(0, 0, N, i);
    }
}; segtree seg;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    seg.init(n);
    for (int i = 0; i < k; i++) {
        int l = left[i], r = right[i], h = height[i];
        if (op[i] == 1)
            seg.maksimum(l, r, h);
        else
            seg.minimum(l, r, h);
    }

    for (int i = 0; i < n; i++) {
        finalHeight[i] = seg.get(i);
    }
}

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