Submission #655274

#	Time	Username	Problem	Language	Result	Execution time	Memory
655274		jophyyjh	Wall (IOI14_wall)	C++14	100 / 100	705 ms	149124 KiB

wall

/**
 * One of the most interesting problems in the year! I began by investigating two
 * consecutive phases. We have:
 *  (1) add(u) + add(v) is equivalent to add(max(u,v));
 *  (2) remove(u) + remove(v) is equivalent to remove(min(u,v));
 *  (3) add(u) + remove(v) (where u > v) changes all values to v;
 *  (4) add(u) + remove(v) (where u <= v) increases values <u to u, decreases values
 *      >v to v, and keeps values in [u,v] unchanged;
 *  (5) remove(v) + add(u) (where u <= v) does the same as (4).
 * In particular, (4) & (5) aroused my interest. Indeed, when we picture a set of
 * points placed on the real number line at 0,1,2,...,T, we see that after applying
 * the k operations to all points, the resultant points still form a contigous
 * range.
 * 
 * Now, I'll formally describe my solution. Let an "active range" [a,b] be an
 * operation which:
 *      increases values <a to a, decreases values >b to b, and keeps the
 *      remaining values unchanged.
 * We now claim that the combination of a few phases is equivalent to an active
 * range. For example, add(3) + remove(4) => [3,4], while add(3) + remove(2)
 * + add(4) => [4,4] (case (3), (4)).
 * First, add(val) => [val,INF] and remove(val) => [-INF,val]. (This is (1) & (2).)
 * With some case work, we can then check that the combination of two active range
 * is another active range. (Quite intuitive, I suppose?)
 * 
 * This means that we can maintain a segment tree with nodes which are "active
 * ranges". Its underlying array should have q active ranges, each one representing
 * a phase. By default, all of the q underlying nodes are "inactive" (set to
 * [-INF,INF]). We'll turn them active by setting one of the underlying range to the
 * one corresponding to the actual phase. We then traverse from 0 to n-1, each time
 * computing finalHeight[i] with the overall active range (at the root of the tree).
 * As each phase operates on a contigous range, we have to modify the seg tree by
 * O(k) times. Nice problem~
 * 
 * Note that a much more difficult problem would be to support range addition &
 * max/min operations. It's especially difficult to do it online. In fact, the only
 * resouce I've seen which mentions it is p99 of
 * http://82.156.16.222/media/ds91m7uwn31s8rlqtsra.pdf.
 * 
 * Time Complexity: O(n + k * log(k))       (Full solution)
 * Implementation 1         (Offline algorithm, Segment Tree)
*/
 
#include <bits/stdc++.h>
#include "wall.h"

typedef std::vector<int>    vec;

int H_MAX = 1e5;

// A type 1 segment tree
template<class T> struct SegTree {
    int n;
    std::vector<T> tree;
    SegTree(int _n, const T& identity) {
        n = _n;
        tree.assign(4 * n, identity);
    }
    void _update(int pos, const T& val, int k, int i, int j) {
        if (i == j) {
            tree[k] = val;
            return;
        }
        int mid = (i + j) / 2;
        if (pos <= mid)
            _update(pos, val, 2 * k, i, mid);
        else
            _update(pos, val, 2 * k + 1, mid + 1, j);
        tree[k] = merge(tree[2 * k], tree[2 * k + 1]);
    }
    inline void update(int pos, const T& val)   { _update(pos, val, 1, 0, n - 1); }
};


struct range_t {
    int l, r;
};

const range_t ID = {0, H_MAX};

range_t merge(const range_t& r1, const range_t& r2) {
    assert(r1.l <= r1.r && r2.l <= r2.r);
    if (r1.r <= r2.l)
        return range_t{r2.l, r2.l};
    else if (r2.r <= r1.l)
        return range_t{r2.r, r2.r};
    else
        return range_t{std::max(r1.l, r2.l), std::min(r1.r, r2.r)};
}

void buildWall(int n, int q, int op[], int l[], int r[], int h[], int ans[]) {
    std::vector<vec> add(n + 1), remove(n + 1);
    for (int i = 0; i < q; i++) {
        add[l[i]].push_back(i);
        remove[r[i] + 1].push_back(i);
    }
    SegTree<range_t> tree(q, ID);       // all default to inactive
    for (int i = 0; i < n; i++) {
        for (int qi : add[i]) {
            if (op[qi] == 1)
                tree.update(qi, range_t{h[qi], H_MAX});
            else
                tree.update(qi, range_t{0, h[qi]});
        }
        for (int qi : remove[i])
            tree.update(qi, ID);
        ans[i] = tree.tree[1].l;
    }
}

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