oj.uz

Submission #198605

# Submission time Handle Problem Language Result Execution time Memory
198605 2020-01-26T22:17:35 Z DS007 Wall (IOI14_wall) C++14
100 / 100
 1767 ms 123792 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), upper[v] = min(upper[v], lower[v]);
        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 44 ms 62968 KB Output is correct
2 Correct 46 ms 62968 KB Output is correct
3 Correct 48 ms 62968 KB Output is correct
4 Correct 54 ms 63352 KB Output is correct
5 Correct 50 ms 63224 KB Output is correct
6 Correct 50 ms 63224 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 62968 KB Output is correct
2 Correct 219 ms 70776 KB Output is correct
3 Correct 276 ms 66680 KB Output is correct
4 Correct 730 ms 72828 KB Output is correct
5 Correct 407 ms 73464 KB Output is correct
6 Correct 418 ms 73384 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 62968 KB Output is correct
2 Correct 49 ms 62964 KB Output is correct
3 Correct 44 ms 62968 KB Output is correct
4 Correct 51 ms 63224 KB Output is correct
5 Correct 49 ms 63224 KB Output is correct
6 Correct 52 ms 63352 KB Output is correct
7 Correct 45 ms 63096 KB Output is correct
8 Correct 217 ms 70908 KB Output is correct
9 Correct 270 ms 66700 KB Output is correct
10 Correct 717 ms 72824 KB Output is correct
11 Correct 424 ms 73312 KB Output is correct
12 Correct 402 ms 73284 KB Output is correct
13 Correct 45 ms 62968 KB Output is correct
14 Correct 214 ms 70904 KB Output is correct
15 Correct 79 ms 64504 KB Output is correct
16 Correct 700 ms 82672 KB Output is correct
17 Correct 417 ms 82168 KB Output is correct
18 Correct 408 ms 82168 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 63096 KB Output is correct
2 Correct 46 ms 62968 KB Output is correct
3 Correct 47 ms 62968 KB Output is correct
4 Correct 49 ms 63224 KB Output is correct
5 Correct 49 ms 63352 KB Output is correct
6 Correct 49 ms 63224 KB Output is correct
7 Correct 44 ms 62968 KB Output is correct
8 Correct 217 ms 70768 KB Output is correct
9 Correct 268 ms 66768 KB Output is correct
10 Correct 712 ms 72776 KB Output is correct
11 Correct 412 ms 73340 KB Output is correct
12 Correct 411 ms 73336 KB Output is correct
13 Correct 45 ms 63096 KB Output is correct
14 Correct 224 ms 70844 KB Output is correct
15 Correct 83 ms 64504 KB Output is correct
16 Correct 716 ms 82692 KB Output is correct
17 Correct 426 ms 82244 KB Output is correct
18 Correct 416 ms 82144 KB Output is correct
19 Correct 1767 ms 123792 KB Output is correct
20 Correct 1328 ms 121200 KB Output is correct
21 Correct 1401 ms 123772 KB Output is correct
22 Correct 1075 ms 121280 KB Output is correct
23 Correct 1101 ms 121308 KB Output is correct
24 Correct 1529 ms 121156 KB Output is correct
25 Correct 1697 ms 121252 KB Output is correct
26 Correct 1186 ms 123748 KB Output is correct
27 Correct 1452 ms 123712 KB Output is correct
28 Correct 1705 ms 121100 KB Output is correct
29 Correct 1086 ms 121136 KB Output is correct
30 Correct 1342 ms 121264 KB Output is correct