oj.uz

Submission #160107

# Submission time Handle Problem Language Result Execution time Memory
160107 2019-10-26T02:58:12 Z rama_pang Wall (IOI14_wall) C++14
0 / 100
 229 ms 14096 KB 
#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) {}

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

    };

    vector<Node> tree;

    segtree() {}

    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_min, 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_min, tree[n].lazy_min);

            tree[n * 2].lazy_min = tree[n].lazy_min;
            tree[n * 2 + 1].lazy_min = 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_min, 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_min, tree[n].lazy_max);

            tree[n * 2].lazy_max = tree[n].lazy_max;
            tree[n * 2 + 1].lazy_max = tree[n].lazy_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;
            }

            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;
            }
            
            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);
        return;
    }

    int query(int n, int tl, int tr, int p) {
        if (tl == tr) {
            assert(tree[n].val_max == tree[n].val_min);
            assert(p == tl);
            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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 508 KB Output is correct
3 Incorrect 3 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 184 ms 14096 KB Output is correct
3 Incorrect 229 ms 8696 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Incorrect 3 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Incorrect 3 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -