oj.uz

Submission #198604

# Submission time Handle Problem Language Result Execution time Memory
198604 2020-01-26T22:06:13 Z DS007 Wall (IOI14_wall) C++14
32 / 100
 738 ms 73464 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), lower[v] = 1e9;
        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 + 8 * 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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 62968 KB Output is correct
2 Correct 39 ms 62968 KB Output is correct
3 Correct 38 ms 62968 KB Output is correct
4 Correct 43 ms 63224 KB Output is correct
5 Correct 46 ms 63224 KB Output is correct
6 Correct 44 ms 63352 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 62968 KB Output is correct
2 Correct 215 ms 70880 KB Output is correct
3 Correct 270 ms 66808 KB Output is correct
4 Correct 738 ms 72872 KB Output is correct
5 Correct 405 ms 73336 KB Output is correct
6 Correct 389 ms 73336 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 62968 KB Output is correct
2 Correct 40 ms 62968 KB Output is correct
3 Correct 39 ms 62968 KB Output is correct
4 Correct 43 ms 63224 KB Output is correct
5 Correct 43 ms 63224 KB Output is correct
6 Correct 44 ms 63224 KB Output is correct
7 Correct 39 ms 62968 KB Output is correct
8 Correct 213 ms 70776 KB Output is correct
9 Correct 265 ms 66788 KB Output is correct
10 Correct 715 ms 72952 KB Output is correct
11 Correct 405 ms 73464 KB Output is correct
12 Correct 400 ms 73336 KB Output is correct
13 Correct 39 ms 62968 KB Output is correct
14 Incorrect 216 ms 70776 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 62968 KB Output is correct
2 Correct 42 ms 62968 KB Output is correct
3 Correct 41 ms 62968 KB Output is correct
4 Correct 44 ms 63352 KB Output is correct
5 Correct 42 ms 63352 KB Output is correct
6 Correct 42 ms 63224 KB Output is correct
7 Correct 39 ms 62968 KB Output is correct
8 Correct 214 ms 70904 KB Output is correct
9 Correct 256 ms 66680 KB Output is correct
10 Correct 697 ms 72772 KB Output is correct
11 Correct 415 ms 73336 KB Output is correct
12 Correct 407 ms 73464 KB Output is correct
13 Correct 41 ms 62968 KB Output is correct
14 Incorrect 219 ms 70776 KB Output isn't correct
15 Halted 0 ms 0 KB -