Submission #160113

#	Time	Username	Problem	Language	Result	Execution time	Memory
160113		rama_pang	Wall (IOI14_wall)	C++14	100 / 100	1644 ms	162284 KiB

wall

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

/*  Keep a lower bound and upper bound of heights in each node of
    segment tree. To propagate, just get the values of the parent
    node and update its lower bound and upper bound. For query, just
    traverse through the segment tree for each node (point query).
*/

struct segtree {
    struct Node {
        int val_min, val_max;
        int lazy_min; // val_min and val_max should not be lower than this
        int lazy_max; // val_min and val_max should not be higher than this

        Node(): val_min(0), val_max(0), lazy_min(-1), lazy_max(-1) {}

    };

    vector<Node> tree;

    inline void lazydown(int n) {
        if (tree[n].lazy_min != -1) {
            tree[n * 2].val_min = max(tree[n * 2].val_min, tree[n].lazy_min);
            tree[n * 2].val_max = max(tree[n * 2].val_max, tree[n].lazy_min);
            
            tree[n * 2 + 1].val_min = max(tree[n * 2 + 1].val_min, tree[n].lazy_min);
            tree[n * 2 + 1].val_max = max(tree[n * 2 + 1].val_max, tree[n].lazy_min);
        }

        if (tree[n].lazy_max != -1) {
            tree[n * 2].val_min = min(tree[n * 2].val_min, tree[n].lazy_max);
            tree[n * 2].val_max = min(tree[n * 2].val_max, tree[n].lazy_max);

            tree[n * 2 + 1].val_min = min(tree[n * 2 + 1].val_min, tree[n].lazy_max);
            tree[n * 2 + 1].val_max = min(tree[n * 2 + 1].val_max, tree[n].lazy_max);
        }

        tree[n * 2].lazy_min = tree[n * 2].val_min;
        tree[n * 2].lazy_max = tree[n * 2].val_max;

        tree[n * 2 + 1].lazy_min = tree[n * 2 + 1].val_min;
        tree[n * 2 + 1].lazy_max = tree[n * 2 + 1].val_max;
        
        tree[n].lazy_min = tree[n].lazy_max = -1;
    }

    void init(int n) {
        tree.resize(4 * n + 5);
    }

    void update(int n, int tl, int tr, int le, int ri, int val, int type) {
        if (tl > tr || tl > ri || tr < le) return;
        if (le <= tl && tr <= ri) {
            if (type == 1) { // add
                tree[n].val_max = max(tree[n].val_max, val);
                tree[n].val_min = max(tree[n].val_min, val);
                tree[n].lazy_min = tree[n].val_min;
                tree[n].lazy_max = tree[n].val_max;
            }

            if (type == 2) { // remove
                tree[n].val_max = min(tree[n].val_max, val);
                tree[n].val_min = min(tree[n].val_min, val);
                tree[n].lazy_max = tree[n].val_max;
                tree[n].lazy_min = tree[n].val_min;
            }
            
            return;
        }

        int mid = (tl + tr) / 2;
        lazydown(n);
        update(n * 2, tl, mid, le, ri, val, type);
        update(n * 2 + 1, mid + 1, tr, le, ri, val, type);
        tree[n].val_min = min(tree[n * 2].val_min, tree[n * 2 + 1].val_min);
        tree[n].val_max = max(tree[n * 2].val_max, tree[n * 2 + 1].val_max);
    }

    int query(int n, int tl, int tr, int p) {
        if (tl == tr) return tree[n].val_min;

        int mid = (tl + tr) / 2;
        lazydown(n);
        if (p <= mid) 
            return query(n * 2, tl, mid, p);
        else 
            return query(n * 2 + 1, mid + 1, tr, p);
    }

} solver;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    solver.init(n);
    for (int i = 0; i < k; i++) solver.update(1, 0, n - 1, left[i], right[i], height[i], op[i]);
    for (int i = 0; i < n; i++) finalHeight[i] = solver.query(1, 0, n - 1, i);
    return;
}

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