oj.uz

Submission #198603

# Submission time Handle Problem Language Result Execution time Memory
198603 2020-01-26T22:04:06 Z DS007 Wall (IOI14_wall) C++14
32 / 100
 1198 ms 52216 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 + 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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31608 KB Output is correct
2 Correct 24 ms 31736 KB Output is correct
3 Correct 23 ms 31736 KB Output is correct
4 Correct 29 ms 32120 KB Output is correct
5 Correct 26 ms 32120 KB Output is correct
6 Correct 28 ms 32120 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31736 KB Output is correct
2 Correct 197 ms 39548 KB Output is correct
3 Correct 252 ms 39288 KB Output is correct
4 Correct 683 ms 51192 KB Output is correct
5 Correct 388 ms 52216 KB Output is correct
6 Correct 387 ms 50680 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31608 KB Output is correct
2 Correct 23 ms 31736 KB Output is correct
3 Correct 23 ms 31736 KB Output is correct
4 Correct 27 ms 32124 KB Output is correct
5 Correct 29 ms 32120 KB Output is correct
6 Correct 30 ms 32060 KB Output is correct
7 Correct 23 ms 31608 KB Output is correct
8 Correct 200 ms 45280 KB Output is correct
9 Correct 243 ms 39160 KB Output is correct
10 Correct 698 ms 51192 KB Output is correct
11 Correct 387 ms 52216 KB Output is correct
12 Correct 399 ms 50556 KB Output is correct
13 Correct 22 ms 31608 KB Output is correct
14 Incorrect 197 ms 45328 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31608 KB Output is correct
2 Correct 34 ms 31736 KB Output is correct
3 Correct 23 ms 31736 KB Output is correct
4 Correct 29 ms 32120 KB Output is correct
5 Correct 27 ms 32120 KB Output is correct
6 Correct 26 ms 32120 KB Output is correct
7 Correct 22 ms 31608 KB Output is correct
8 Correct 203 ms 45304 KB Output is correct
9 Correct 249 ms 39160 KB Output is correct
10 Correct 729 ms 51220 KB Output is correct
11 Correct 521 ms 52216 KB Output is correct
12 Correct 1198 ms 50680 KB Output is correct
13 Correct 24 ms 31608 KB Output is correct
14 Incorrect 203 ms 45304 KB Output isn't correct
15 Halted 0 ms 0 KB -