oj.uz

Submission #700311

# Submission time Handle Problem Language Result Execution time Memory
700311 2023-02-19T05:09:07 Z Forested Wall (IOI14_wall) C++17
100 / 100
 738 ms 48784 KB 
#include "wall.h"

#include <bits/stdc++.h>
using namespace std;

using i32 = int;
using i64 = long long;
template <typename T>
using Vec = vector<T>;

#define OVERRIDE4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i)
#define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define ALL(x) begin(x), end(x)
#define PER(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)

template <typename T>
bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    } else {
        return false;
    }
}
template <typename T>
bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    } else {
        return false;
    }
}

constexpr i32 INF = 1001001001;
constexpr i64 INF64 = 3003003003003003003;

i32 ceil_pow2(i32 n) {
    i32 k = 1;
    while (k < n) {
        k *= 2;
    }
    return k;
}

struct Func {
    i32 lo, hi;
};

Func id() {
    return Func{-INF, INF};
}
Func composite(Func f, Func g) {
    if (f.lo > g.hi) {
        return Func{f.lo, f.lo};
    }
    if (f.hi < g.lo) {
        return Func{f.hi, f.hi};
    }
    return Func{max(f.lo, g.lo), min(f.hi, g.hi)};
}

class DualSegmentTree {
    i32 n;
    Vec<Func> funcs;
    
    void push(i32 idx) {
        if (idx < n) {
            funcs[2 * idx] = composite(funcs[idx], funcs[2 * idx]);
            funcs[2 * idx + 1] = composite(funcs[idx], funcs[2 * idx + 1]);
            funcs[idx] = id();
        }
    }
    
    void _apply(i32 l, i32 r, Func f, i32 cur, i32 curl, i32 curr) {
        if (curr <= l || r <= curl) {
            return;
        }
        if (l <= curl && curr <= r) {
            funcs[cur] = composite(f, funcs[cur]);
            return;
        }
        i32 curm = (curl + curr) / 2;
        push(cur);
        _apply(l, r, f, 2 * cur, curl, curm);
        _apply(l, r, f, 2 * cur + 1, curm, curr);
    }
    
public:
    DualSegmentTree(i32 n_) : n(ceil_pow2(n_)), funcs(2 * n, id()) {}
    
    void apply(i32 l, i32 r, Func f) {
        _apply(l, r, f, 1, 0, n);
    }
    
    Func get(i32 idx) const {
        idx += n;
        Func ret = id();
        while (idx > 0) {
            ret = composite(funcs[idx], ret);
            idx /= 2;
        }
        return ret;
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    DualSegmentTree seg(n);
    REP(i, k) {
        if (op[i] == 1) {
            seg.apply(left[i], right[i] + 1, Func{height[i], INF});
        } else {
            seg.apply(left[i], right[i] + 1, Func{-INF, height[i]});
        }
    }
    REP(i, n) {
        Func f = seg.get(i);
        finalHeight[i] = (0 < f.lo ? f.lo : 0 > f.hi ? f.hi : 0);
    }
}

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 212 KB Output is correct
4 Correct 8 ms 596 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 4 ms 596 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 130 ms 8052 KB Output is correct
3 Correct 157 ms 4124 KB Output is correct
4 Correct 398 ms 10568 KB Output is correct
5 Correct 286 ms 10596 KB Output is correct
6 Correct 266 ms 10568 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 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 8 ms 596 KB Output is correct
5 Correct 7 ms 596 KB Output is correct
6 Correct 13 ms 664 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 128 ms 8188 KB Output is correct
9 Correct 137 ms 4128 KB Output is correct
10 Correct 457 ms 10564 KB Output is correct
11 Correct 271 ms 10572 KB Output is correct
12 Correct 240 ms 10512 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 144 ms 8216 KB Output is correct
15 Correct 36 ms 1276 KB Output is correct
16 Correct 576 ms 10484 KB Output is correct
17 Correct 240 ms 10568 KB Output is correct
18 Correct 259 ms 10568 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 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 6 ms 596 KB Output is correct
5 Correct 6 ms 664 KB Output is correct
6 Correct 5 ms 596 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 137 ms 8016 KB Output is correct
9 Correct 138 ms 4120 KB Output is correct
10 Correct 381 ms 10572 KB Output is correct
11 Correct 296 ms 10572 KB Output is correct
12 Correct 267 ms 10576 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 139 ms 8048 KB Output is correct
15 Correct 30 ms 1320 KB Output is correct
16 Correct 607 ms 10564 KB Output is correct
17 Correct 317 ms 10568 KB Output is correct
18 Correct 249 ms 10460 KB Output is correct
19 Correct 731 ms 48736 KB Output is correct
20 Correct 644 ms 48732 KB Output is correct
21 Correct 716 ms 48776 KB Output is correct
22 Correct 652 ms 48764 KB Output is correct
23 Correct 682 ms 48784 KB Output is correct
24 Correct 737 ms 48712 KB Output is correct
25 Correct 664 ms 48720 KB Output is correct
26 Correct 731 ms 48772 KB Output is correct
27 Correct 734 ms 48784 KB Output is correct
28 Correct 738 ms 48676 KB Output is correct
29 Correct 703 ms 48684 KB Output is correct
30 Correct 704 ms 48688 KB Output is correct