oj.uz

Submission #683505

# Submission time Handle Problem Language Result Execution time Memory
683505 2023-01-18T15:45:56 Z speedyArda Wall (IOI14_wall) C++14
100 / 100
 934 ms 99360 KB 
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 2e6 + 5;
const int inf = 1e9 + 7;
 
struct Node {
    int mx = inf;
    int mn = 0;
    Node()
    {

    };
} 
seg[MAXN * 4];
 
void push(int v)
{
    seg[2 * v].mn = min(seg[v].mx, max(seg[v * 2].mn, seg[v].mn));
    seg[2 * v].mx = max(seg[v].mn, min(seg[2 * v].mx, seg[v].mx));
    seg[2 * v + 1].mn = min(seg[v].mx, max(seg[v * 2 + 1].mn, seg[v].mn));
    seg[2 * v + 1].mx = max(seg[v].mn, min(seg[2 * v + 1].mx, seg[v].mx));
    seg[v].mn = 0;
    seg[v].mx = inf;
}

void update(int v, int tl, int tr, int l, int r, int val, int type)
{
    if(l > r)
        return;
    if(l <= tl && r >= tr)
    {
        if(type == 1)
        {
            seg[v].mx = max(seg[v].mx, val);
            seg[v].mn = max(seg[v].mn, val);
        } else 
        {
            seg[v].mx = min(seg[v].mx, val);
            seg[v].mn = min(seg[v].mn, val);
        }
        return;
    }

    push(v);

    int tm = (tl + tr) / 2;
    update(2 * v, tl, tm, l, min(tm, r), val, type);
    update(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, val, type);
}

int get(int v, int tl, int tr, int pos)
{
    if(tl == tr)
        return seg[v].mn;
    push(v);

    int tm = (tl + tr) / 2;
    if(tm >= pos)
        return get(2 * v, tl, tm, pos);
    else
        return get(2 * v + 1, tm + 1, tr, pos);
}
 
 
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]);
    }
    
    for (int i = 0; i < n; i++) {
        finalHeight[i] = get(1, 0, n - 1, i);
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 62828 KB Output is correct
2 Correct 29 ms 63036 KB Output is correct
3 Correct 31 ms 62980 KB Output is correct
4 Correct 38 ms 63128 KB Output is correct
5 Correct 35 ms 63120 KB Output is correct
6 Correct 32 ms 63052 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 62804 KB Output is correct
2 Correct 157 ms 76496 KB Output is correct
3 Correct 161 ms 70068 KB Output is correct
4 Correct 413 ms 80840 KB Output is correct
5 Correct 286 ms 82000 KB Output is correct
6 Correct 299 ms 80448 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 62804 KB Output is correct
2 Correct 30 ms 62932 KB Output is correct
3 Correct 32 ms 62888 KB Output is correct
4 Correct 35 ms 63124 KB Output is correct
5 Correct 33 ms 63120 KB Output is correct
6 Correct 33 ms 63144 KB Output is correct
7 Correct 33 ms 62828 KB Output is correct
8 Correct 153 ms 76464 KB Output is correct
9 Correct 169 ms 69992 KB Output is correct
10 Correct 403 ms 80932 KB Output is correct
11 Correct 285 ms 81980 KB Output is correct
12 Correct 271 ms 80364 KB Output is correct
13 Correct 29 ms 62848 KB Output is correct
14 Correct 167 ms 76480 KB Output is correct
15 Correct 51 ms 64068 KB Output is correct
16 Correct 404 ms 81228 KB Output is correct
17 Correct 301 ms 80588 KB Output is correct
18 Correct 286 ms 80516 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 62892 KB Output is correct
2 Correct 33 ms 63016 KB Output is correct
3 Correct 34 ms 62900 KB Output is correct
4 Correct 40 ms 63108 KB Output is correct
5 Correct 35 ms 63108 KB Output is correct
6 Correct 38 ms 63096 KB Output is correct
7 Correct 29 ms 62876 KB Output is correct
8 Correct 155 ms 76524 KB Output is correct
9 Correct 162 ms 70124 KB Output is correct
10 Correct 434 ms 81024 KB Output is correct
11 Correct 275 ms 81928 KB Output is correct
12 Correct 276 ms 80384 KB Output is correct
13 Correct 31 ms 62804 KB Output is correct
14 Correct 153 ms 76480 KB Output is correct
15 Correct 52 ms 64024 KB Output is correct
16 Correct 437 ms 81128 KB Output is correct
17 Correct 276 ms 80552 KB Output is correct
18 Correct 309 ms 80676 KB Output is correct
19 Correct 879 ms 99360 KB Output is correct
20 Correct 896 ms 96820 KB Output is correct
21 Correct 887 ms 99348 KB Output is correct
22 Correct 862 ms 96804 KB Output is correct
23 Correct 902 ms 96800 KB Output is correct
24 Correct 930 ms 96816 KB Output is correct
25 Correct 870 ms 96884 KB Output is correct
26 Correct 859 ms 99308 KB Output is correct
27 Correct 865 ms 99236 KB Output is correct
28 Correct 934 ms 96856 KB Output is correct
29 Correct 877 ms 96728 KB Output is correct
30 Correct 893 ms 96732 KB Output is correct