Submission #1215892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215892		Captain_Georgia	Wall (IOI14_wall)	C++20	100 / 100	546 ms	55192 KiB

wall

#include "wall.h"

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

typedef long long ll;

struct Lazy_Segtree {
    #define left v + 1
    #define right v + 2 * (tm - tl)
    struct pi {
        int l = 0, r = 1e9 + 99;
    } emp;
    vector<pi> tree;
    void init (int x) {
        tree.assign (x << 1, emp);
    }

    void built (int v, int tl, int tr, vector<int> &arr) {
        if (tl + 1 == tr) {
            tree[v].l = tree[v].r = arr[tl];
            return;
        }
        int tm = (tl + tr) >> 1;
        built(left, tl, tm, arr);
        built(right, tm, tr, arr);
    }
    void push(int v, int tl, int tr) {
        if (tl + 1 == tr) return;

        int tm = (tl + tr) >> 1;
        tree[left].l = max(tree[left].l, tree[v].l);
        tree[left].r = max(tree[left].r, tree[left].l);
        tree[left].r = min(tree[left].r, tree[v].r);
        tree[left].l = min(tree[left].l, tree[left].r);

        tree[right].l = max(tree[right].l, tree[v].l);
        tree[right].r = max(tree[right].r, tree[right].l);
        tree[right].r = min(tree[right].r, tree[v].r);
        tree[right].l = min(tree[right].l, tree[right].r);

        tree[v].l = 0;
        tree[v].r = 1e9 + 99;
    }
    void update1 (int v, int tl, int tr, int ql, int qr, int val) {
        if (ql >= tr || tl >= qr) {
            return;
        }
        if (ql <= tl && tr <= qr) {
            tree[v].l = max(tree[v].l, val);
            tree[v].r = max(tree[v].r, tree[v].l);
            tree[v].l = min(tree[v].l, tree[v].r);
            return;
        }
        push(v, tl, tr);
        int tm = (tl + tr) >> 1;
        update1(left, tl, tm, ql, qr, val);
        update1(right, tm, tr, ql, qr, val);
    }
    void update2 (int v, int tl, int tr, int ql, int qr, int val) {
        if (ql >= tr || tl >= qr) {
            return;
        }
        if (ql <= tl && tr <= qr) {
            tree[v].r = max(tree[v].r, tree[v].l);
            tree[v].r = min(tree[v].r, val);
            tree[v].l = min(tree[v].l, tree[v].r);
            return;
        }
        push(v, tl, tr);
        int tm = (tl + tr) >> 1;
        update2(left, tl, tm, ql, qr, val);
        update2(right, tm, tr, ql, qr, val);
    }
    ll get (int v, int tl, int tr, int pos) {
        if (tl + 1 == tr) {
            return tree[v].l;
        }
        push(v, tl, tr);
        int tm = (tl + tr) >> 1;
        if (pos < tm) return get(left, tl, tm, pos);
        return get(right, tm, tr, pos);
    }
};

void buildWall (int N, int K, int op[], int L[], int R[], int height[], int finalHeight[]) {

    vector<int> arr(N, 0);

    Lazy_Segtree LST;
    LST.init(N + 10);
    LST.built(0, 0, N, arr);
    for (int i = 0;i < K;i ++) {
        if (op[i] == 1) {
            LST.update1(0, 0, N, L[i], R[i] + 1, height[i]);
        } else {
            LST.update2(0, 0, N, L[i], R[i] + 1, height[i]);
        }
        // for (int j = 0;j < N;j ++) cout << LST.get(0, 0, N, j) << " ";
        // cout << "\n";
    }
    for (int i = 0;i < N;i ++) finalHeight[i] = LST.get(0, 0, N, i);
}

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