oj.uz

Submission #655271

# Submission time Handle Problem Language Result Execution time Memory
655271 2022-11-03T17:08:14 Z jophyyjh Wall (IOI14_wall) C++14
100 / 100
 700 ms 159588 KB 
/**
 * 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~
 * 
 * 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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 572 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 6 ms 1364 KB Output is correct
5 Correct 5 ms 1268 KB Output is correct
6 Correct 5 ms 1236 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 214 ms 33768 KB Output is correct
3 Correct 228 ms 17992 KB Output is correct
4 Correct 598 ms 47820 KB Output is correct
5 Correct 301 ms 46300 KB Output is correct
6 Correct 306 ms 44364 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 5 ms 1364 KB Output is correct
5 Correct 5 ms 1236 KB Output is correct
6 Correct 6 ms 1272 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 212 ms 33928 KB Output is correct
9 Correct 184 ms 18060 KB Output is correct
10 Correct 600 ms 47908 KB Output is correct
11 Correct 299 ms 46312 KB Output is correct
12 Correct 336 ms 44372 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 218 ms 33724 KB Output is correct
15 Correct 29 ms 3936 KB Output is correct
16 Correct 647 ms 47856 KB Output is correct
17 Correct 333 ms 44844 KB Output is correct
18 Correct 321 ms 44508 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 568 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 5 ms 1364 KB Output is correct
5 Correct 5 ms 1236 KB Output is correct
6 Correct 5 ms 1272 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 214 ms 33708 KB Output is correct
9 Correct 188 ms 18020 KB Output is correct
10 Correct 700 ms 47812 KB Output is correct
11 Correct 300 ms 46336 KB Output is correct
12 Correct 307 ms 44448 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 217 ms 33736 KB Output is correct
15 Correct 27 ms 3924 KB Output is correct
16 Correct 629 ms 47968 KB Output is correct
17 Correct 334 ms 44780 KB Output is correct
18 Correct 346 ms 44496 KB Output is correct
19 Correct 575 ms 159412 KB Output is correct
20 Correct 595 ms 159500 KB Output is correct
21 Correct 575 ms 159412 KB Output is correct
22 Correct 562 ms 159492 KB Output is correct
23 Correct 575 ms 159380 KB Output is correct
24 Correct 587 ms 159588 KB Output is correct
25 Correct 594 ms 159440 KB Output is correct
26 Correct 572 ms 159392 KB Output is correct
27 Correct 542 ms 159424 KB Output is correct
28 Correct 550 ms 159416 KB Output is correct
29 Correct 566 ms 159388 KB Output is correct
30 Correct 577 ms 159456 KB Output is correct