oj.uz

Submission #741630

# Submission time Handle Problem Language Result Execution time Memory
741630 2023-05-14T13:37:12 Z vjudge1 Wall (IOI14_wall) C++17
100 / 100
 617 ms 74288 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 852 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 4 ms 852 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 116 ms 8140 KB Output is correct
3 Correct 131 ms 4172 KB Output is correct
4 Correct 367 ms 18488 KB Output is correct
5 Correct 292 ms 19044 KB Output is correct
6 Correct 254 ms 19020 KB Output is correct

Subtask #3
29.0 / 29.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 5 ms 828 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 121 ms 13940 KB Output is correct
9 Correct 137 ms 8048 KB Output is correct
10 Correct 386 ms 18520 KB Output is correct
11 Correct 252 ms 19120 KB Output is correct
12 Correct 244 ms 19000 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 127 ms 13936 KB Output is correct
15 Correct 24 ms 2000 KB Output is correct
16 Correct 368 ms 18804 KB Output is correct
17 Correct 237 ms 18744 KB Output is correct
18 Correct 248 ms 18812 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 7 ms 852 KB Output is correct
5 Correct 4 ms 832 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 122 ms 13948 KB Output is correct
9 Correct 136 ms 8136 KB Output is correct
10 Correct 354 ms 18492 KB Output is correct
11 Correct 243 ms 19012 KB Output is correct
12 Correct 240 ms 19020 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 129 ms 13956 KB Output is correct
15 Correct 22 ms 2012 KB Output is correct
16 Correct 380 ms 18772 KB Output is correct
17 Correct 245 ms 18848 KB Output is correct
18 Correct 237 ms 18740 KB Output is correct
19 Correct 596 ms 74288 KB Output is correct
20 Correct 612 ms 71720 KB Output is correct
21 Correct 591 ms 74208 KB Output is correct
22 Correct 589 ms 71784 KB Output is correct
23 Correct 578 ms 71784 KB Output is correct
24 Correct 587 ms 71756 KB Output is correct
25 Correct 592 ms 71716 KB Output is correct
26 Correct 559 ms 74284 KB Output is correct
27 Correct 596 ms 74288 KB Output is correct
28 Correct 612 ms 71848 KB Output is correct
29 Correct 572 ms 71824 KB Output is correct
30 Correct 617 ms 71812 KB Output is correct