oj.uz

Submission #737898

# Submission time Handle Problem Language Result Execution time Memory
737898 2023-05-07T22:43:27 Z applemethod69 Wall (IOI14_wall) C++14
0 / 100
 3000 ms 18424 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) {
        cerr << node << " " << val << endl;
        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 (-lazy2[node] < lazy1[node]) {
                        lazy1[node] = min(lazy1[node], val);
                    } else {
                        lazy1[node] = val;
                    }
                    swap(lazy1[node], lazy2[node]);
                }
            } 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++) {
        finalHeight[i] = segtree.query(1, 0, n - 1, i);
    }
    return;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 300 KB Output is correct
2 Correct 29 ms 564 KB Output is correct
3 Incorrect 244 ms 828 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2387 ms 18424 KB Output is correct
3 Execution timed out 3072 ms 16100 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 39.0

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