oj.uz

Submission #474136

# Submission time Handle Problem Language Result Execution time Memory
474136 2021-09-17T02:03:15 Z jalsol Wall (IOI14_wall) C++17
100 / 100
 859 ms 99396 KB 
// looking to shine brighter in this world...

#define TASK "wall"
#include "wall.h"

#ifdef LOCAL
#include "local.h"
#else
#include <bits/stdc++.h>
#define debug(...)
#define DB(...)
#endif

using namespace std;

using ll = long long;
using ld = long double;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fi first
#define se second

#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)
#define Fe(...) for (auto __VA_ARGS__)

template <class C> inline int isz(const C& c) { return static_cast<int>(c.size()); }
template <class T> inline bool chmin(T& a, const T& b) { return (a > b) ? a = b, true : false; }
template <class T> inline bool chmax(T& a, const T& b) { return (a < b) ? a = b, true : false; }

const bool __initialization = []() {
    cin.tie(nullptr)->sync_with_stdio(false);
    if (fopen(TASK".inp", "r")) {
        (void)(!freopen(TASK".inp", "r", stdin));
        (void)(!freopen(TASK".out", "w", stdout)); }
    cout << setprecision(12) << fixed;
    return true;
}();

constexpr ld eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;

// =============================================================================

constexpr int maxn = 2e6 + 5;

struct Node {
    int mn, mx;
    Node() : mn(inf), mx(0) {}
    Node(int lo, int hi) : mn(lo), mx(hi) {}

    void update(int lo, int hi) {
        chmin(mn, lo);
        mx = max(min(mx, lo), hi);
    }
};

int n, k;
Node tree[maxn << 2];

void push(int i) {
    tree[i << 1].update(tree[i].mn, tree[i].mx);
    tree[i << 1 | 1].update(tree[i].mn, tree[i].mx);
    tree[i] = { inf, 0 };
}

void update(int u, int v, int op, int val, int i = 1, int l = 0, int r = n - 1) {
    if (v < l || r < u) return;

    if (u <= l && r <= v) {
        if (op == 1) {
            tree[i].update(inf, val);
        }
        else {
            tree[i].update(val, 0);
        }

        return;
    }

    push(i);
    int m = (l + r) / 2;
    update(u, v, op, val, i << 1, l, m);
    update(u, v, op, val, i << 1 | 1, m + 1, r);
}

void build(int ans[], int i = 1, int l = 0, int r = n - 1) {
    if (l == r) {
        ans[l] = tree[i].mx;
        return;
    }

    push(i);
    int m = (l + r) / 2;
    build(ans, i << 1, l, m);
    build(ans, i << 1 | 1, m + 1, r);
}

void buildWall(int N, int K, int op[], int l[], int r[], int h[], int ans[]) {
    { n = N; k = K; }

    Rep (i, k) {
        update(l[i], r[i], op[i], h[i]);
    }

    build(ans);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 62924 KB Output is correct
2 Correct 34 ms 62960 KB Output is correct
3 Correct 35 ms 62964 KB Output is correct
4 Correct 38 ms 63160 KB Output is correct
5 Correct 37 ms 63096 KB Output is correct
6 Correct 38 ms 63080 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 62812 KB Output is correct
2 Correct 193 ms 76612 KB Output is correct
3 Correct 209 ms 70056 KB Output is correct
4 Correct 596 ms 80940 KB Output is correct
5 Correct 416 ms 81988 KB Output is correct
6 Correct 333 ms 80384 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 62900 KB Output is correct
2 Correct 40 ms 63048 KB Output is correct
3 Correct 34 ms 62916 KB Output is correct
4 Correct 39 ms 63108 KB Output is correct
5 Correct 37 ms 63060 KB Output is correct
6 Correct 49 ms 63176 KB Output is correct
7 Correct 32 ms 62924 KB Output is correct
8 Correct 178 ms 76528 KB Output is correct
9 Correct 217 ms 70080 KB Output is correct
10 Correct 600 ms 80928 KB Output is correct
11 Correct 412 ms 82004 KB Output is correct
12 Correct 347 ms 80324 KB Output is correct
13 Correct 38 ms 62920 KB Output is correct
14 Correct 194 ms 76480 KB Output is correct
15 Correct 71 ms 64036 KB Output is correct
16 Correct 729 ms 81144 KB Output is correct
17 Correct 340 ms 80568 KB Output is correct
18 Correct 349 ms 80568 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 62808 KB Output is correct
2 Correct 36 ms 63008 KB Output is correct
3 Correct 42 ms 62928 KB Output is correct
4 Correct 41 ms 63072 KB Output is correct
5 Correct 38 ms 63192 KB Output is correct
6 Correct 38 ms 63172 KB Output is correct
7 Correct 34 ms 62820 KB Output is correct
8 Correct 183 ms 76476 KB Output is correct
9 Correct 253 ms 70084 KB Output is correct
10 Correct 607 ms 80916 KB Output is correct
11 Correct 430 ms 82028 KB Output is correct
12 Correct 375 ms 80480 KB Output is correct
13 Correct 39 ms 62916 KB Output is correct
14 Correct 186 ms 76672 KB Output is correct
15 Correct 69 ms 64128 KB Output is correct
16 Correct 727 ms 81256 KB Output is correct
17 Correct 376 ms 80564 KB Output is correct
18 Correct 342 ms 80544 KB Output is correct
19 Correct 824 ms 99284 KB Output is correct
20 Correct 859 ms 96708 KB Output is correct
21 Correct 746 ms 99256 KB Output is correct
22 Correct 754 ms 96828 KB Output is correct
23 Correct 739 ms 96832 KB Output is correct
24 Correct 764 ms 96820 KB Output is correct
25 Correct 768 ms 96944 KB Output is correct
26 Correct 755 ms 99396 KB Output is correct
27 Correct 754 ms 99268 KB Output is correct
28 Correct 752 ms 96708 KB Output is correct
29 Correct 746 ms 96800 KB Output is correct
30 Correct 735 ms 96836 KB Output is correct