Submission #713698

#	Time	Username	Problem	Language	Result	Execution time	Memory
713698		thimote75	Wall (IOI14_wall)	C++14	0 / 100	149 ms	13888 KiB

wall

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

#define INF 1e9

struct SGD {
    int min_v = - INF;
    int max_v = INF;

    int to (int x) {
        return max(min_v, min(max_v, x));
    }
    void combine (SGD &upper) {
        min_v = upper.to(min_v);
        max_v = upper.to(max_v);
    }
    void reset () {
        min_v = - INF;
        max_v = INF;
    }
};

struct SegTree {
    vector<SGD> tree;

    int size, start, height;
    SegTree (int _size) {
        size = _size;

        height = ceil(log2(size));
        start  = 1 << height;

        tree.resize(start << 1);
    }

    void update (int index) {
        if (index == 0)     return ;
        if (index >= start) return ;

        update (index << 1);

        int n0 = index << 1;
        int n1 = n0 + 1;

        tree[n0].combine(tree[index]);
        tree[n1].combine(tree[index]);
        tree[index].reset();
    }
    void set_min (int index, int min_v) {
        update(index);
        //printf("min %d %d\n", index, min_v);

        tree[index].min_v = min_v;
    }
    void set_max (int index, int max_v) {
        update(index);
        //printf("min %d %d\n", index, min_v);

        tree[index].max_v = max_v;
    }

    void set_min (int left, int right, int min_v) {
        left += start; right += start;

        while (left < right) {
            if ((left  & 1) == 1) set_min(left,  min_v);
            if ((right & 1) == 0) set_min(right, min_v);

            left  = (left  + 1) >> 1;
            right = (right - 1) >> 1;
        }

        if (left == right) set_min(left, min_v);
    }
    void set_max (int left, int right, int max_v) {
        left += start; right += start;

        while (left < right) {
            if ((left  & 1) == 1) set_max(left,  max_v);
            if ((right & 1) == 0) set_max(right, max_v);

            left  = (left  + 1) >> 1;
            right = (right - 1) >> 1;
        }

        if (left == right) set_max(left, max_v);
    }

    int res (int index, int height) {
        index += start;
        update(index);

        return tree[index].to(height);
    }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    SegTree tree(n);

    for (int i = 0; i < k; i ++) {
        if (op[1] == 1) {
            tree.set_min( left[i], right[i], height[i] );
        } else tree.set_max( left[i], right[i], height[i] );
    }

    for (int i = 0; i < n; i ++)
        finalHeight[i] = tree.res(i, height[i]);
}

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