oj.uz

Submission #583745

# Submission time Handle Problem Language Result Execution time Memory
583745 2022-06-26T07:21:34 Z Drew_ Wall (IOI14_wall) C++17
100 / 100
 660 ms 69452 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define f1 first
#define s2 second

using ii = pair<int, int>;

const int MAX = 2e6 + 69;
const int inf = 1e9 + 69;

ii st[1 << 22]; // [up, down]
void add(int p, int q, int u, int d, int node, int l, int r)
{
    if (l > q || r < p)
        return;
    if (p <= l && r <= q)
    {
        st[node].f1 = max(st[node].f1, u);
        st[node].s2 = max(st[node].s2, u);
        st[node].f1 = min(st[node].f1, d);
        st[node].s2 = min(st[node].s2, d);
        return;
    }

    int mid = (l + r) >> 1;    
    st[node << 1].f1 = max(st[node << 1].f1, st[node].f1);
    st[node << 1].f1 = min(st[node << 1].f1, st[node].s2);
    st[node << 1].s2 = max(st[node << 1].s2, st[node].f1);
    st[node << 1].s2 = min(st[node << 1].s2, st[node].s2);

    st[node << 1 | 1].f1 = max(st[node << 1 | 1].f1, st[node].f1);
    st[node << 1 | 1].f1 = min(st[node << 1 | 1].f1, st[node].s2);
    st[node << 1 | 1].s2 = max(st[node << 1 | 1].s2, st[node].f1);
    st[node << 1 | 1].s2 = min(st[node << 1 | 1].s2, st[node].s2);

    st[node] = { 0, inf };

    add(p, q, u, d, node << 1, l, mid);
    add(p, q, u, d, node << 1 | 1, mid+1, r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    fill(st, st + (1 << 22), mp(0, inf));
    for (int i = 0; i < k; ++i)
    {
        if (op[i] == 1)
            add(left[i], right[i], height[i], inf, 1, 0, n-1);
        else add(left[i], right[i], 0, height[i], 1, 0, n-1);
    }

    const auto getAns = [&](const auto &self, int node, int l, int r) -> void
    {
        if (l == r)
        {
            finalHeight[l] = min(st[node].f1, st[node].s2);
            return;
        }
        int mid = (l + r) >> 1;
        st[node << 1].f1 = max(st[node << 1].f1, st[node].f1);
        st[node << 1].f1 = min(st[node << 1].f1, st[node].s2);
        st[node << 1].s2 = max(st[node << 1].s2, st[node].f1);
        st[node << 1].s2 = min(st[node << 1].s2, st[node].s2);

        st[node << 1 | 1].f1 = max(st[node << 1 | 1].f1, st[node].f1);
        st[node << 1 | 1].f1 = min(st[node << 1 | 1].f1, st[node].s2);
        st[node << 1 | 1].s2 = max(st[node << 1 | 1].s2, st[node].f1);
        st[node << 1 | 1].s2 = min(st[node << 1 | 1].s2, st[node].s2);

        st[node] = { 0, inf };

        self(self, node << 1, l, mid);
        self(self, node << 1 | 1, mid+1, r);
    };
    getAns(getAns, 1, 0, n-1);

    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 33108 KB Output is correct
2 Correct 20 ms 33228 KB Output is correct
3 Correct 20 ms 33136 KB Output is correct
4 Correct 21 ms 33368 KB Output is correct
5 Correct 26 ms 33336 KB Output is correct
6 Correct 18 ms 33364 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 33108 KB Output is correct
2 Correct 175 ms 46816 KB Output is correct
3 Correct 171 ms 40252 KB Output is correct
4 Correct 436 ms 51080 KB Output is correct
5 Correct 284 ms 52172 KB Output is correct
6 Correct 279 ms 50588 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 33108 KB Output is correct
2 Correct 18 ms 33152 KB Output is correct
3 Correct 17 ms 33108 KB Output is correct
4 Correct 20 ms 33356 KB Output is correct
5 Correct 19 ms 33308 KB Output is correct
6 Correct 18 ms 33320 KB Output is correct
7 Correct 19 ms 33076 KB Output is correct
8 Correct 153 ms 46668 KB Output is correct
9 Correct 189 ms 40320 KB Output is correct
10 Correct 412 ms 51080 KB Output is correct
11 Correct 270 ms 52140 KB Output is correct
12 Correct 291 ms 50560 KB Output is correct
13 Correct 16 ms 33108 KB Output is correct
14 Correct 160 ms 46780 KB Output is correct
15 Correct 38 ms 34252 KB Output is correct
16 Correct 442 ms 51404 KB Output is correct
17 Correct 271 ms 50764 KB Output is correct
18 Correct 292 ms 50724 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33108 KB Output is correct
2 Correct 16 ms 33236 KB Output is correct
3 Correct 17 ms 33120 KB Output is correct
4 Correct 21 ms 33356 KB Output is correct
5 Correct 25 ms 33268 KB Output is correct
6 Correct 21 ms 33272 KB Output is correct
7 Correct 17 ms 33080 KB Output is correct
8 Correct 158 ms 46832 KB Output is correct
9 Correct 165 ms 40176 KB Output is correct
10 Correct 413 ms 51128 KB Output is correct
11 Correct 303 ms 52168 KB Output is correct
12 Correct 279 ms 50580 KB Output is correct
13 Correct 19 ms 33040 KB Output is correct
14 Correct 164 ms 46724 KB Output is correct
15 Correct 36 ms 34252 KB Output is correct
16 Correct 396 ms 51416 KB Output is correct
17 Correct 290 ms 50732 KB Output is correct
18 Correct 274 ms 50824 KB Output is correct
19 Correct 631 ms 69444 KB Output is correct
20 Correct 620 ms 66916 KB Output is correct
21 Correct 627 ms 69444 KB Output is correct
22 Correct 600 ms 67024 KB Output is correct
23 Correct 619 ms 66988 KB Output is correct
24 Correct 643 ms 67032 KB Output is correct
25 Correct 612 ms 66916 KB Output is correct
26 Correct 660 ms 69452 KB Output is correct
27 Correct 620 ms 69448 KB Output is correct
28 Correct 621 ms 66960 KB Output is correct
29 Correct 650 ms 67016 KB Output is correct
30 Correct 632 ms 67060 KB Output is correct