oj.uz

Submission #771864

# Submission time Handle Problem Language Result Execution time Memory
771864 2023-07-03T10:38:42 Z PanosPask Wall (IOI14_wall) C++14
100 / 100
 517 ms 69572 KB 
#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

struct SegTree {
    struct Node {
        int above;
        int below;
    };

    const int NO_OP = -1;
    const Node NEUTRAL = {0, INT_MAX};

    void make_mod(Node& a, Node op) {
        if (op.below < a.above) {
            a.above = op.below;
            a.below = op.below;
        }
        if (op.above > a.below) {
            a.below = op.above;
            a.above = op.above;
        }
        else {
            a.above = max(op.above, a.above);
            a.below = min(op.below, a.below);
        }

    }

    int size;
    vector<Node> tree;

    void init(int n) {
        size = 1;
        while (size < n)
            size *= 2;

        tree.assign(2 * size, NEUTRAL);
    }

    void propagate(int x) {
        make_mod(tree[2 * x + 1], tree[x]);
        make_mod(tree[2 * x + 2], tree[x]);

        tree[x] = NEUTRAL;
    }

    void modify(int l, int r, Node& v, int x, int lx, int rx) {
        if (l >= rx || lx >= r) {
            return;
        }
        else if (l <= lx && rx <= r) {
            make_mod(tree[x], v);
            return;
        }

        propagate(x);

        int mid = (lx + rx) / 2;
        modify(l, r, v, 2 * x + 1, lx, mid);
        modify(l, r, v, 2 * x + 2, mid, rx);
    }
    void add(int l, int r, int h) {
        Node v;
        v.above = h;
        v.below = INT_MAX;

        modify(l, r, v, 0, 0, size);
    }
    void remove(int l, int r, int h) {
        Node v;
        v.below = h;
        v.above = 0;

        modify(l, r, v, 0, 0, size);
    }

    void print_all(int n, int f[], int x, int lx, int rx) {
        if (lx == rx - 1) {
            if (lx >= n)
                return;

            int v;
            v = tree[x].above;

            f[lx] = v;
            return;
        }

        propagate(x);

        int mid = (lx + rx) / 2;
        print_all(n, f, 2 * x + 1, lx, mid);
        print_all(n, f, 2 * x + 2, mid, rx);

        return;
    }
    void print_all(int n, int f[]) {
        print_all(n, f, 0, 0, size);
    }
};

SegTree st;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    st.init(n);

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

    }
    st.print_all(n, finalHeight);

    return;
}

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 340 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 5 ms 724 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 110 ms 13916 KB Output is correct
3 Correct 134 ms 7940 KB Output is correct
4 Correct 351 ms 20308 KB Output is correct
5 Correct 218 ms 21424 KB Output is correct
6 Correct 212 ms 19856 KB Output is correct

Subtask #3
29.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 1 ms 340 KB Output is correct
4 Correct 5 ms 824 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 110 ms 13832 KB Output is correct
9 Correct 129 ms 7884 KB Output is correct
10 Correct 356 ms 20304 KB Output is correct
11 Correct 219 ms 21308 KB Output is correct
12 Correct 210 ms 19744 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 119 ms 13868 KB Output is correct
15 Correct 26 ms 1940 KB Output is correct
16 Correct 460 ms 20576 KB Output is correct
17 Correct 221 ms 20196 KB Output is correct
18 Correct 220 ms 19984 KB Output is correct

Subtask #4
39.0 / 39.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 340 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 820 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 115 ms 13940 KB Output is correct
9 Correct 128 ms 7904 KB Output is correct
10 Correct 352 ms 20288 KB Output is correct
11 Correct 223 ms 21452 KB Output is correct
12 Correct 212 ms 19788 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 115 ms 13872 KB Output is correct
15 Correct 26 ms 2012 KB Output is correct
16 Correct 462 ms 20560 KB Output is correct
17 Correct 233 ms 19980 KB Output is correct
18 Correct 225 ms 20032 KB Output is correct
19 Correct 517 ms 69448 KB Output is correct
20 Correct 502 ms 66888 KB Output is correct
21 Correct 506 ms 69480 KB Output is correct
22 Correct 495 ms 67012 KB Output is correct
23 Correct 492 ms 66924 KB Output is correct
24 Correct 494 ms 66940 KB Output is correct
25 Correct 497 ms 67100 KB Output is correct
26 Correct 495 ms 69572 KB Output is correct
27 Correct 502 ms 69404 KB Output is correct
28 Correct 498 ms 67016 KB Output is correct
29 Correct 491 ms 67016 KB Output is correct
30 Correct 504 ms 66972 KB Output is correct