oj.uz

Submission #713708

# Submission time Handle Problem Language Result Execution time Memory
713708 2023-03-22T21:00:56 Z thimote75 Wall (IOI14_wall) C++14
8 / 100
 3000 ms 20300 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 i = 0; i < n; i ++)
    //    finalHeight[i] = tree.res(i, 0);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 23 ms 692 KB Output is correct
5 Correct 23 ms 696 KB Output is correct
6 Correct 23 ms 724 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 130 ms 8012 KB Output is correct
3 Correct 1546 ms 4132 KB Output is correct
4 Execution timed out 3050 ms 20144 KB Time limit exceeded
5 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 2 ms 340 KB Output is correct
3 Correct 3 ms 328 KB Output is correct
4 Correct 25 ms 696 KB Output is correct
5 Correct 22 ms 752 KB Output is correct
6 Correct 23 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 131 ms 13836 KB Output is correct
9 Correct 1552 ms 7968 KB Output is correct
10 Execution timed out 3056 ms 20180 KB Time limit exceeded
11 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 Correct 2 ms 340 KB Output is correct
4 Correct 23 ms 724 KB Output is correct
5 Correct 25 ms 724 KB Output is correct
6 Correct 23 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 145 ms 13908 KB Output is correct
9 Correct 1532 ms 7980 KB Output is correct
10 Execution timed out 3057 ms 20300 KB Time limit exceeded
11 Halted 0 ms 0 KB -