oj.uz

Submission #742187

# Submission time Handle Problem Language Result Execution time Memory
742187 2023-05-15T17:59:15 Z Blagoj Wall (IOI14_wall) C++14
100 / 100
 616 ms 67004 KB 
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()

struct Node {
    int mn = 0, mx = 0;
};

Node seg[2 * (1 << 21) + 20];
int ans[2000005];

void lz(int k) {
    seg[k * 2].mn = min(seg[k * 2].mn, seg[k].mn);
    seg[k * 2].mn = max(seg[k * 2].mn, seg[k].mx);
    seg[k * 2].mx = min(seg[k * 2].mx, seg[k].mn);
    seg[k * 2].mx = max(seg[k * 2].mx, seg[k].mx);
    seg[k * 2 + 1].mn = min(seg[k * 2 + 1].mn, seg[k].mn);
    seg[k * 2 + 1].mn = max(seg[k * 2 + 1].mn, seg[k].mx);
    seg[k * 2 + 1].mx = min(seg[k * 2 + 1].mx, seg[k].mn);
    seg[k * 2 + 1].mx = max(seg[k * 2 + 1].mx, seg[k].mx);
}

void update(int k, int l, int r, int i, int j, int v, int t) {
    if (l > j || r < i) return;
    if (i <= l && r <= j) {
        if (t == 1) {
            seg[k].mn = max(seg[k].mn, v);
            seg[k].mx = max(seg[k].mx, v);
        }
        else {
            seg[k].mn = min(seg[k].mn, v);
            seg[k].mx = min(seg[k].mx, v);
        }
        return;
    }
    lz(k);
    seg[k].mn = 2000010;
    seg[k].mx = 0;
    update(k * 2, l, (l + r) / 2, i, j, v, t);
    update(k * 2 + 1, (l + r) / 2 + 1, r, i, j, v, t);
}

void get(int k, int l, int r) {
    if (l == r) {
        ans[l] = seg[k].mn;
        return;
    }
    lz(k);
    get(k * 2, l, (l + r) / 2);
    get(k * 2 + 1, (l + r) / 2 + 1, r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    for (int i = 0; i < k; i++) {
        update(1, 0, n - 1, left[i], right[i], height[i], op[i]);
    }
    get(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 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 680 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 134 ms 8056 KB Output is correct
3 Correct 144 ms 4156 KB Output is correct
4 Correct 384 ms 11148 KB Output is correct
5 Correct 240 ms 11660 KB Output is correct
6 Correct 241 ms 11576 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 121 ms 8084 KB Output is correct
9 Correct 135 ms 4260 KB Output is correct
10 Correct 360 ms 11208 KB Output is correct
11 Correct 240 ms 11608 KB Output is correct
12 Correct 239 ms 11620 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 117 ms 8152 KB Output is correct
15 Correct 21 ms 1448 KB Output is correct
16 Correct 361 ms 11440 KB Output is correct
17 Correct 266 ms 11368 KB Output is correct
18 Correct 237 ms 11348 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 121 ms 8136 KB Output is correct
9 Correct 137 ms 4220 KB Output is correct
10 Correct 367 ms 11092 KB Output is correct
11 Correct 237 ms 11632 KB Output is correct
12 Correct 237 ms 11700 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 125 ms 8136 KB Output is correct
15 Correct 31 ms 1484 KB Output is correct
16 Correct 355 ms 11336 KB Output is correct
17 Correct 237 ms 11340 KB Output is correct
18 Correct 241 ms 11364 KB Output is correct
19 Correct 578 ms 66904 KB Output is correct
20 Correct 574 ms 64332 KB Output is correct
21 Correct 582 ms 66940 KB Output is correct
22 Correct 576 ms 64308 KB Output is correct
23 Correct 616 ms 64368 KB Output is correct
24 Correct 568 ms 64444 KB Output is correct
25 Correct 592 ms 64332 KB Output is correct
26 Correct 609 ms 66868 KB Output is correct
27 Correct 591 ms 67004 KB Output is correct
28 Correct 563 ms 64392 KB Output is correct
29 Correct 566 ms 64292 KB Output is correct
30 Correct 562 ms 64376 KB Output is correct