Submission #738501

#	Time	Username	Problem	Language	Result	Execution time	Memory
738501		applemethod69	Wall (IOI14_wall)	C++14	100 / 100	967 ms	122320 KiB

wall

#include <bits/stdc++.h>

#include "wall.h"

using namespace std;

using ll = long long;

class SegmentTree {
  public:
    int size;
    vector<int> nodes;
    vector<int> lazy1, lazy2;
    vector<bool> has_lazy1, has_lazy2;

    SegmentTree(int n) : size(n), nodes(4 * n), lazy1(4 * n), lazy2(4 * n), has_lazy1(4 * n), has_lazy2(4 * n) {}

    void update_node(int node, int val) {
        if (val > 0) {
            nodes[node] = min(nodes[node], val - 1);
        } else {
            nodes[node] = max(nodes[node], -val - 1);
        }
        if (has_lazy1[node]) {
            if (has_lazy2[node]) {
                if ((ll)lazy2[node] * val > 0) {
                    lazy2[node] = min(lazy2[node], val);
                } else {
                    if (lazy1[node] + lazy2[node] > 0) {
                        swap(lazy1[node], lazy2[node]);
                        lazy2[node] = min(lazy2[node], val);
                    } else if (val + lazy2[node] < 0) {
                        lazy1[node] = lazy2[node];
                        lazy2[node] = val;
                    }
                }
            } else {
                if ((ll)lazy1[node] * val > 0) {
                    lazy1[node] = min(lazy1[node], val);
                } else {
                    lazy2[node] = val;
                    has_lazy2[node] = true;
                }
            }
        } else {
            lazy1[node] = val;
            has_lazy1[node] = true;
        }
    }

    void propagate(int node) {
        if (has_lazy1[node]) {
            update_node(2 * node, lazy1[node]);
            update_node(2 * node + 1, lazy1[node]);
            has_lazy1[node] = false;
        }
        if (has_lazy2[node]) {
            update_node(2 * node, lazy2[node]);
            update_node(2 * node + 1, lazy2[node]);
            has_lazy2[node] = false;
        }
    }

    void update(int node, int node_left, int node_right, int update_left, int update_right, int val) {
        if (node_left >= update_left && node_right <= update_right) {
            update_node(node, val);
            return;
        }
        int mid = (node_left + node_right) / 2;
        propagate(node);
        if (update_left <= mid) {
            update(2 * node, node_left, mid, update_left, update_right, val);
        }
        if (update_right > mid) {
            update(2 * node + 1, mid + 1, node_right, update_left, update_right, val);
        }
        nodes[node] = max(nodes[2 * node], nodes[2 * node + 1]);
    }

    int query(int node, int node_left, int node_right, int query_ind) {
        if (node_left == node_right && node_left == query_ind) {
            return nodes[node];
        }
        int mid = (node_left + node_right) / 2;
        propagate(node);
        if (query_ind <= mid) {
            return query(2 * node, node_left, mid, query_ind);
        } else {
            return query(2 * node + 1, mid + 1, node_right, query_ind);
        }
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    SegmentTree segtree(n);
    for (int i = 0; i < k; i++) {
        segtree.update(1, 0, n - 1, left[i], right[i], (height[i] + 1) * (2 * op[i] - 3));
        // for (int i = 0; i < n; i++) {
        //     std::cerr << segtree.query(1, 0, n - 1, i) << " ";
        // }
        // std::cerr << std::endl;
    }
    for (int i = 0; i < n; i++) {
        finalHeight[i] = segtree.query(1, 0, n - 1, i);
    }
    return;
}

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