oj.uz

Submission #198602

# Submission time Handle Problem Language Result Execution time Memory
198602 2020-01-26T22:00:57 Z DS007 Wall (IOI14_wall) C++14
0 / 100
 196 ms 45192 KB 
#include <bits/stdc++.h>
#include <wall.h>
using namespace std;

const int N = 2e6;
int upper[N * 8], lower[N * 8], ans[N];

void push(int v) {
    upper[v] = min(upper[v], lower[v]);
    upper[v * 2] = min(upper[v * 2], lower[v * 2]);
    upper[v * 2 + 1] = min(upper[v * 2 + 1], lower[v * 2 + 1]);
    upper[v * 2] = max(upper[v * 2], upper[v]);
    upper[v * 2 + 1] = max(upper[v * 2 + 1], upper[v]);
    lower[v * 4] = min(lower[v * 2], lower[v * 4]);
    lower[v * 4 + 1] = min(lower[v * 4 + 1], lower[v * 2]);
    lower[v * 4 + 2] = min(lower[v * 4 + 2], lower[v * 2 + 1]);
    lower[v * 4 + 3] = min(lower[v * 4 + 3], lower[v * 2 + 1]);
    lower[v * 2] = lower[v];
    lower[v * 2 + 1] = lower[v];
    upper[v] = 0;
    lower[v] = 1e9;
}

void update(int v, int l, int r, int tl, int tr, int val) {
    if (tl > tr)
        return;
    else if (l != r)
        push(v);

    if (l == tl && r == tr) {
        if (val > 0)
            upper[v] = max(upper[v], val);
        else
            lower[v] = min(lower[v], -val);
        return;
    }

    int mid = (l + r) / 2;
    update(v * 2, l, mid, tl, min(mid, tr), val);
    update(v * 2 + 1, mid + 1, r, max(mid + 1, tl), tr, val);
}

void query(int v, int l, int r) {
    if (l == r) {
        ans[l] = min(upper[v], lower[v]);
        return;
    }

    push(v);
    int mid = (l + r) / 2;
    query(v * 2, l, mid);
    query(v * 2 + 1, mid + 1, r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    fill(lower, lower + 4 * N, 1e9);

    for (int i = 0; i < k; i++) {
        if (op[i] == 1)
            update(1, 0, n - 1, left[i], right[i], height[i]);
        else
            update(1, 0, n - 1, left[i], right[i], -height[i]);
    }

    query(1, 0, n - 1);
    for (int i = 0; i < n; i++) finalHeight[i] = ans[i];
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31608 KB Output is correct
2 Incorrect 23 ms 31736 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31736 KB Output is correct
2 Incorrect 196 ms 45192 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31736 KB Output is correct
2 Incorrect 23 ms 31736 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31736 KB Output is correct
2 Incorrect 25 ms 31736 KB Output isn't correct
3 Halted 0 ms 0 KB -