oj.uz

Submission #738501

# Submission time Handle Problem Language Result Execution time Memory
738501 2023-05-09T00:11:40 Z applemethod69 Wall (IOI14_wall) C++14
100 / 100
 967 ms 122320 KB 
#include <bits/stdc++.h>

#include "wall.h"

using namespace std;

using ll = long long;

class SegmentTree {
  public:
    int size;
    vector<int> nodes;
    vector<int> lazy1, lazy2;
    vector<bool> has_lazy1, has_lazy2;

    SegmentTree(int n) : size(n), nodes(4 * n), lazy1(4 * n), lazy2(4 * n), has_lazy1(4 * n), has_lazy2(4 * n) {}

    void update_node(int node, int val) {
        if (val > 0) {
            nodes[node] = min(nodes[node], val - 1);
        } else {
            nodes[node] = max(nodes[node], -val - 1);
        }
        if (has_lazy1[node]) {
            if (has_lazy2[node]) {
                if ((ll)lazy2[node] * val > 0) {
                    lazy2[node] = min(lazy2[node], val);
                } else {
                    if (lazy1[node] + lazy2[node] > 0) {
                        swap(lazy1[node], lazy2[node]);
                        lazy2[node] = min(lazy2[node], val);
                    } else if (val + lazy2[node] < 0) {
                        lazy1[node] = lazy2[node];
                        lazy2[node] = val;
                    }
                }
            } else {
                if ((ll)lazy1[node] * val > 0) {
                    lazy1[node] = min(lazy1[node], val);
                } else {
                    lazy2[node] = val;
                    has_lazy2[node] = true;
                }
            }
        } else {
            lazy1[node] = val;
            has_lazy1[node] = true;
        }
    }

    void propagate(int node) {
        if (has_lazy1[node]) {
            update_node(2 * node, lazy1[node]);
            update_node(2 * node + 1, lazy1[node]);
            has_lazy1[node] = false;
        }
        if (has_lazy2[node]) {
            update_node(2 * node, lazy2[node]);
            update_node(2 * node + 1, lazy2[node]);
            has_lazy2[node] = false;
        }
    }

    void update(int node, int node_left, int node_right, int update_left, int update_right, int val) {
        if (node_left >= update_left && node_right <= update_right) {
            update_node(node, val);
            return;
        }
        int mid = (node_left + node_right) / 2;
        propagate(node);
        if (update_left <= mid) {
            update(2 * node, node_left, mid, update_left, update_right, val);
        }
        if (update_right > mid) {
            update(2 * node + 1, mid + 1, node_right, update_left, update_right, val);
        }
        nodes[node] = max(nodes[2 * node], nodes[2 * node + 1]);
    }

    int query(int node, int node_left, int node_right, int query_ind) {
        if (node_left == node_right && node_left == query_ind) {
            return nodes[node];
        }
        int mid = (node_left + node_right) / 2;
        propagate(node);
        if (query_ind <= mid) {
            return query(2 * node, node_left, mid, query_ind);
        } else {
            return query(2 * node + 1, mid + 1, node_right, query_ind);
        }
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    SegmentTree segtree(n);
    for (int i = 0; i < k; i++) {
        segtree.update(1, 0, n - 1, left[i], right[i], (height[i] + 1) * (2 * op[i] - 3));
        // for (int i = 0; i < n; i++) {
        //     std::cerr << segtree.query(1, 0, n - 1, i) << " ";
        // }
        // std::cerr << std::endl;
    }
    for (int i = 0; i < n; i++) {
        finalHeight[i] = segtree.query(1, 0, n - 1, i);
    }
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 2 ms 356 KB Output is correct
4 Correct 10 ms 980 KB Output is correct
5 Correct 6 ms 980 KB Output is correct
6 Correct 5 ms 952 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 144 ms 13896 KB Output is correct
3 Correct 228 ms 8268 KB Output is correct
4 Correct 633 ms 23004 KB Output is correct
5 Correct 267 ms 23500 KB Output is correct
6 Correct 286 ms 21892 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 9 ms 980 KB Output is correct
5 Correct 5 ms 980 KB Output is correct
6 Correct 5 ms 952 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 133 ms 13868 KB Output is correct
9 Correct 212 ms 8160 KB Output is correct
10 Correct 679 ms 22920 KB Output is correct
11 Correct 301 ms 23464 KB Output is correct
12 Correct 241 ms 21904 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 137 ms 13832 KB Output is correct
15 Correct 56 ms 2192 KB Output is correct
16 Correct 930 ms 23044 KB Output is correct
17 Correct 280 ms 22344 KB Output is correct
18 Correct 300 ms 22344 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 308 KB Output is correct
4 Correct 10 ms 884 KB Output is correct
5 Correct 7 ms 980 KB Output is correct
6 Correct 6 ms 948 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 151 ms 13884 KB Output is correct
9 Correct 230 ms 8268 KB Output is correct
10 Correct 631 ms 22924 KB Output is correct
11 Correct 321 ms 23520 KB Output is correct
12 Correct 248 ms 21896 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 143 ms 13900 KB Output is correct
15 Correct 51 ms 2184 KB Output is correct
16 Correct 967 ms 22920 KB Output is correct
17 Correct 320 ms 22344 KB Output is correct
18 Correct 259 ms 22340 KB Output is correct
19 Correct 891 ms 122228 KB Output is correct
20 Correct 828 ms 122276 KB Output is correct
21 Correct 835 ms 122280 KB Output is correct
22 Correct 843 ms 122260 KB Output is correct
23 Correct 837 ms 122320 KB Output is correct
24 Correct 900 ms 122276 KB Output is correct
25 Correct 882 ms 122304 KB Output is correct
26 Correct 871 ms 122272 KB Output is correct
27 Correct 839 ms 122276 KB Output is correct
28 Correct 905 ms 122300 KB Output is correct
29 Correct 882 ms 122284 KB Output is correct
30 Correct 832 ms 122272 KB Output is correct