Submission #771864

#	Time	Username	Problem	Language	Result	Execution time	Memory
771864		PanosPask	Wall (IOI14_wall)	C++14	100 / 100	517 ms	69572 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

struct SegTree {
    struct Node {
        int above;
        int below;
    };

    const int NO_OP = -1;
    const Node NEUTRAL = {0, INT_MAX};

    void make_mod(Node& a, Node op) {
        if (op.below < a.above) {
            a.above = op.below;
            a.below = op.below;
        }
        if (op.above > a.below) {
            a.below = op.above;
            a.above = op.above;
        }
        else {
            a.above = max(op.above, a.above);
            a.below = min(op.below, a.below);
        }

    }

    int size;
    vector<Node> tree;

    void init(int n) {
        size = 1;
        while (size < n)
            size *= 2;

        tree.assign(2 * size, NEUTRAL);
    }

    void propagate(int x) {
        make_mod(tree[2 * x + 1], tree[x]);
        make_mod(tree[2 * x + 2], tree[x]);

        tree[x] = NEUTRAL;
    }

    void modify(int l, int r, Node& v, int x, int lx, int rx) {
        if (l >= rx || lx >= r) {
            return;
        }
        else if (l <= lx && rx <= r) {
            make_mod(tree[x], v);
            return;
        }

        propagate(x);

        int mid = (lx + rx) / 2;
        modify(l, r, v, 2 * x + 1, lx, mid);
        modify(l, r, v, 2 * x + 2, mid, rx);
    }
    void add(int l, int r, int h) {
        Node v;
        v.above = h;
        v.below = INT_MAX;

        modify(l, r, v, 0, 0, size);
    }
    void remove(int l, int r, int h) {
        Node v;
        v.below = h;
        v.above = 0;

        modify(l, r, v, 0, 0, size);
    }

    void print_all(int n, int f[], int x, int lx, int rx) {
        if (lx == rx - 1) {
            if (lx >= n)
                return;

            int v;
            v = tree[x].above;

            f[lx] = v;
            return;
        }

        propagate(x);

        int mid = (lx + rx) / 2;
        print_all(n, f, 2 * x + 1, lx, mid);
        print_all(n, f, 2 * x + 2, mid, rx);

        return;
    }
    void print_all(int n, int f[]) {
        print_all(n, f, 0, 0, size);
    }
};

SegTree st;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    st.init(n);

    for (int i = 0; i < k; i++) {
        if (op[i] == 1) {
            st.add(left[i], right[i] + 1, height[i]);
        }
        else {
            st.remove(left[i], right[i] + 1, height[i]);
        }

    }
    st.print_all(n, finalHeight);

    return;
}

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