oj.uz

Submission #713710

# Submission time Handle Problem Language Result Execution time Memory
713710 2023-03-22T21:04:33 Z thimote75 Wall (IOI14_wall) C++14
0 / 100
 264 ms 8044 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

#define INF 1e9

struct SGD {
    int min_v = 0;
    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 = 0;
        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);

        for (int i = 0; i < start; i ++)
            tree[i + start].max_v = 0;
    }

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

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

        tree[index].min_v = min_v;
        if (tree[index].max_v < tree[index].min_v)
            tree[index].max_v = tree[index].min_v;
    }
    void set_max (int index, int max_v) {
        update(index);

        tree[index].max_v = max_v;
        if (tree[index].min_v > tree[index].max_v)
            tree[index].min_v = tree[index].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 show (SGD &s) {
        if (s.min_v == -INF) cout << "-";
        else cout << s.min_v;
        cout << ":";
        if (s.max_v == +INF) cout << "+";
        else cout << s.max_v;
        cout << " ";
    }
    void show () {
        for (int h = 0; h <= height; h ++) {
            int s = 1 << h;

            for (int i = 0; i < s; i ++) {
                show(tree[i + s]);
            }
            cout << endl;
        }
    }
    SGD compile (int index) {
        if (index == 0) return SGD();

        SGD upper = compile(index >> 1);
        SGD curr  = tree[index];
        curr.combine(upper);

        return curr;
    }
    void ushow () {
        for (int i = 0; i < start; i ++) {
            int j = i + start;
            SGD v = compile(j);
            show(v);
        }
        cout << endl;
    }
};
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[i] == 1) {
            tree.set_min( left[i], right[i], height[i] );
        } else tree.set_max( left[i], right[i], height[i] );

        //for (int l = left[i]; l <= right[i]; l ++) {
        //    if (op[i] == 1) finalHeight[l] = max(finalHeight[l], height[i]);
        //    else finalHeight[l] = min(finalHeight[l], height[i]);
        //}
//
        //for (int j = 0; j < n; j ++)
        //    assert(finalHeight[j] == tree.compile(j).to(0));
    }

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

Subtask #1
0 / 8.0

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

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 136 ms 8044 KB Output is correct
3 Incorrect 264 ms 4044 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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