oj.uz

Submission #272746

# Submission time Handle Problem Language Result Execution time Memory
272746 2020-08-18T15:02:59 Z toonewbie Wall (IOI14_wall) C++17
100 / 100
 1292 ms 69780 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

const int INF = 2000000000;
const int maxx = 2000005;

#define mn first
#define mx second

pair <int, int> t[maxx << 2];

void relax(int v, int l, int r) {
    if (l != r) {
        int lc = v << 1, rc = v << 1 | 1;
        t[lc] = {max(min(t[lc].mn, t[v].mn), t[v].mx), max(min(t[lc].mx, t[v].mn), t[v].mx)};
        t[rc] = {max(min(t[rc].mn, t[v].mn), t[v].mx), max(min(t[rc].mx, t[v].mn), t[v].mx)};
    }
}

void update(int v, int l, int r, int i, int j, int val, int oq) {
    relax(v, l, r);
    if (i > r || j < l) {
        return;
    }
    if (i <= l && r <= j) {
        if (oq == 1) {
            t[v].mn = max(t[v].mn, val);
            t[v].mx = max(t[v].mx, val);
        } else {
            t[v].mn = min(t[v].mn, val);
            t[v].mx = min(t[v].mx, val);
        }
        return;
    }
    t[v].mn = INF, t[v].mx = -INF;
    int mid = (l + r) >> 1;
    update(v << 1, l, mid, i, j, val, oq);
    update(v << 1 | 1, mid + 1, r, i, j, val, oq);
}
int query(int v, int l, int r, int i) {
    relax(v, l, r);
    if (l == r) {
        return t[v].mn;
    }
    int mid = (l + r) >> 1;
    if (i <= mid) {
        return query(v << 1, l, mid, i);
    } else {
        return query(v << 1 | 1, mid + 1, r, i);
    }
}

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, 1, n, left[i] + 1, right[i] + 1, height[i], op[i]);
    }
    for (int i = 1; i <= n; i++) {
        finalHeight[i - 1] = query(1, 1, n, i);
    }
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 8 ms 896 KB Output is correct
5 Correct 8 ms 896 KB Output is correct
6 Correct 7 ms 896 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 177 ms 14024 KB Output is correct
3 Correct 207 ms 8056 KB Output is correct
4 Correct 602 ms 20556 KB Output is correct
5 Correct 443 ms 21624 KB Output is correct
6 Correct 384 ms 19856 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 8 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 7 ms 896 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 179 ms 14072 KB Output is correct
9 Correct 216 ms 8184 KB Output is correct
10 Correct 630 ms 20472 KB Output is correct
11 Correct 400 ms 21496 KB Output is correct
12 Correct 392 ms 19960 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 180 ms 13944 KB Output is correct
15 Correct 35 ms 2040 KB Output is correct
16 Correct 581 ms 20684 KB Output is correct
17 Correct 403 ms 20072 KB Output is correct
18 Correct 418 ms 20088 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 11 ms 896 KB Output is correct
5 Correct 11 ms 896 KB Output is correct
6 Correct 7 ms 896 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 180 ms 14072 KB Output is correct
9 Correct 219 ms 8056 KB Output is correct
10 Correct 651 ms 20424 KB Output is correct
11 Correct 488 ms 21452 KB Output is correct
12 Correct 471 ms 19960 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 184 ms 13976 KB Output is correct
15 Correct 47 ms 2040 KB Output is correct
16 Correct 629 ms 20728 KB Output is correct
17 Correct 415 ms 20088 KB Output is correct
18 Correct 395 ms 20088 KB Output is correct
19 Correct 1233 ms 69568 KB Output is correct
20 Correct 1257 ms 67064 KB Output is correct
21 Correct 1216 ms 69780 KB Output is correct
22 Correct 1292 ms 67128 KB Output is correct
23 Correct 1220 ms 67068 KB Output is correct
24 Correct 1164 ms 67104 KB Output is correct
25 Correct 1182 ms 67128 KB Output is correct
26 Correct 1197 ms 69688 KB Output is correct
27 Correct 1215 ms 69516 KB Output is correct
28 Correct 1213 ms 67192 KB Output is correct
29 Correct 1191 ms 67092 KB Output is correct
30 Correct 1262 ms 67044 KB Output is correct