oj.uz

Submission #674946

# Submission time Handle Problem Language Result Execution time Memory
674946 2022-12-26T16:36:18 Z bashkort Wall (IOI14_wall) C++17
100 / 100
 711 ms 69492 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

constexpr int inf = 1e9 + 7;

struct Info {
    int L = 0, R = inf;
    Info(int x, int y) : L(x), R(y) {}
    Info() = default;
};

void apply(Info &a, Info b) {
    if (a.L >= b.R) {
        a.L = a.R = b.R;
    } else if (a.R <= b.L) {
        a.L = a.R = b.L;
    } else {
        a.L = max(a.L, b.L);
        a.R = min(a.R, b.R);
    }
}

vector<Info> t;

int sz = 1;
void init(int n) {
    sz = 1 << __lg(n) + bool(n & (n - 1));
    t.assign(sz << 1, {});
}

void apply(int x, Info b) {
    apply(t[x], b);
}

void push(int x) {
    apply(x << 1, t[x]);
    apply(x << 1 | 1, t[x]);
    t[x] = Info();
}

void rangeApply(int l, int r, Info info, int x = 1, int lx = 0, int rx = sz) {
    if (l >= rx || lx >= r) {
        return;
    }
    if (l <= lx && rx <= r) {
        apply(x, info);
        return;
    }
    push(x);
    int mid = (lx + rx) >> 1;
    rangeApply(l, r, info, x << 1, lx, mid);
    rangeApply(l, r, info, x << 1 | 1, mid, rx);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    init(n);
    for (int i = 0; i < k; ++i) {
        Info info{};
        if (op[i] == 1) {
            info.L = height[i];
        } else {
            info.R = height[i];
        }
        rangeApply(left[i], right[i] + 1, info);
    }
    for (int i = 0; i < n; ++i) {
        Info info(0, 0);
        int x = i + sz;
        while (x > 0) {
            apply(info, t[x]);
            x >>= 1;
        }
        finalHeight[i] = info.L;
    }
}

Compilation message

wall.cpp: In function 'void init(int)':
wall.cpp:29:23: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   29 |     sz = 1 << __lg(n) + bool(n & (n - 1));
      |               ~~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 6 ms 760 KB Output is correct
5 Correct 4 ms 756 KB Output is correct
6 Correct 4 ms 724 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 139 ms 13912 KB Output is correct
3 Correct 153 ms 7968 KB Output is correct
4 Correct 379 ms 20320 KB Output is correct
5 Correct 257 ms 21388 KB Output is correct
6 Correct 246 ms 19800 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 2 ms 440 KB Output is correct
3 Correct 2 ms 316 KB Output is correct
4 Correct 6 ms 772 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 820 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 144 ms 13920 KB Output is correct
9 Correct 144 ms 7880 KB Output is correct
10 Correct 367 ms 20304 KB Output is correct
11 Correct 260 ms 21424 KB Output is correct
12 Correct 311 ms 19916 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 143 ms 13864 KB Output is correct
15 Correct 28 ms 1964 KB Output is correct
16 Correct 543 ms 20568 KB Output is correct
17 Correct 281 ms 19980 KB Output is correct
18 Correct 260 ms 19980 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 3 ms 364 KB Output is correct
4 Correct 6 ms 824 KB Output is correct
5 Correct 6 ms 828 KB Output is correct
6 Correct 6 ms 764 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 134 ms 13848 KB Output is correct
9 Correct 141 ms 7900 KB Output is correct
10 Correct 395 ms 20304 KB Output is correct
11 Correct 257 ms 21452 KB Output is correct
12 Correct 249 ms 19804 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 150 ms 13844 KB Output is correct
15 Correct 36 ms 1996 KB Output is correct
16 Correct 473 ms 20628 KB Output is correct
17 Correct 257 ms 19984 KB Output is correct
18 Correct 258 ms 20024 KB Output is correct
19 Correct 711 ms 69492 KB Output is correct
20 Correct 648 ms 66996 KB Output is correct
21 Correct 673 ms 69480 KB Output is correct
22 Correct 686 ms 66936 KB Output is correct
23 Correct 699 ms 67020 KB Output is correct
24 Correct 644 ms 66968 KB Output is correct
25 Correct 651 ms 66908 KB Output is correct
26 Correct 638 ms 69488 KB Output is correct
27 Correct 670 ms 69476 KB Output is correct
28 Correct 635 ms 67040 KB Output is correct
29 Correct 638 ms 66884 KB Output is correct
30 Correct 636 ms 66896 KB Output is correct