oj.uz

Submission #640886

# Submission time Handle Problem Language Result Execution time Memory
640886 2022-09-15T13:32:05 Z Sharky Wall (IOI14_wall) C++17
100 / 100
 799 ms 100332 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

using node = pair<int, int>;
#define mn first
#define mx second
const int inf = 1E9+7;

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

struct segtree {
    int size = 1;
    vector<node> seg, lazy;
    vector<int> ans;
    void init(int N) {
        while (size < N) size *= 2;
        seg.assign(2 * size, {0, 0});
        lazy.assign(2 * size, {0, 0});
        ans.assign(size + 1, 0);
    }
    void add(int id, int x) {
        ckmax(seg[id].mn, x);
        ckmax(seg[id].mx, x);
        ckmax(lazy[id].mn, x);
        ckmax(lazy[id].mx, x);
    }
    void rem(int id, int x) {
        ckmin(seg[id].mn, x);
        ckmin(seg[id].mx, x);
        ckmin(lazy[id].mn, x);
        ckmin(lazy[id].mx, x);
    }
    void push(int id) {
        if (lazy[id].mx != -inf) {
            for (int i = 0; i < 2; i++) {
                add(id * 2 + i, lazy[id].mx);
            }
        }
        if (lazy[id].mn != inf) {
            for (int i = 0; i < 2; i++) {
                rem(id * 2 + i, lazy[id].mn);
            }
        }
        lazy[id] = {inf, -inf};
    }
    node merge(node lhs, node rhs) {
        node rv;
        rv.mn = min(lhs.mn, rhs.mn);
        rv.mx = max(lhs.mx, rhs.mx); 
        return rv;
    }
    void pull(int id) {
        seg[id] = merge(seg[id * 2], seg[id * 2 + 1]);
    }
    void upd(int op, int ql, int qr, int x, int id, int l, int r) {
        if (l > qr || r < ql) return;
        if (ql <= l && r <= qr) {
            if (op == 1) add(id, x);
            else rem(id, x);
            return;
        }
        push(id);
        int mid = (l + r) / 2;
        upd(op, ql, qr, x, id * 2, l, mid);
        upd(op, ql, qr, x, id * 2 + 1, mid + 1, r);
        pull(id);
    }
    void upd(int op, int ql, int qr, int x) {
        upd(op, ql, qr, x, 1, 0, size - 1);
    }
    // node query(int ql, int qr, int id, int l, int r) {
    //     printf("id = %d, l = %d, r = %d\n", id, l, r);
    //     push(id);
    //     if (l > qr || r < ql) return {inf, -inf};
    //     if (ql <= l && r <= qr) return seg[id];
    //     int mid = (l + r) / 2;
    //     node lhs = query(ql, qr, id * 2, l, mid);
    //     node rhs = query(ql, qr, id * 2 + 1, mid + 1, r);
    //     return merge(lhs, rhs);
    // }
    // node query(int ql, int qr) {
    //     return query(ql, qr, 1, 0, size - 1);
    // }
    void calc(int id, int l, int r) {
        if (l == r) ans[l] = seg[id].mn;
        else {
            push(id);
            int mid = (l + r) / 2;
            calc(id * 2, l, mid);
            calc(id * 2 + 1, mid + 1, r);
        }
    }
    void calc() {
        calc(1, 0, size - 1);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    segtree st;
    st.init(n);
    for (int i = 0; i < k; i++) {
        st.upd(op[i], left[i], right[i], height[i]);
    }
    st.calc();
    for (int i = 0; i < n; i++) finalHeight[i] = st.ans[i];
}

#ifndef EVAL

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, q;
    cin >> n >> q;
    segtree st;
    st.init(n);
    while (q--) {
        int op, l, r, h;
        cin >> op >> l >> r >> h;
        st.upd(op, l, r, h);
    }
    st.calc();
    for (int i = 0; i < n; i++) {
        cout << st.ans[i] << "\n";
    }

    return 0;
}

#endif

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 3 ms 340 KB Output is correct
4 Correct 10 ms 980 KB Output is correct
5 Correct 5 ms 980 KB Output is correct
6 Correct 6 ms 980 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 132 ms 8064 KB Output is correct
3 Correct 214 ms 4672 KB Output is correct
4 Correct 610 ms 22744 KB Output is correct
5 Correct 309 ms 23204 KB Output is correct
6 Correct 307 ms 21732 KB Output is correct

Subtask #3
29.0 / 29.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 2 ms 340 KB Output is correct
4 Correct 8 ms 980 KB Output is correct
5 Correct 5 ms 1012 KB Output is correct
6 Correct 6 ms 980 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 132 ms 13904 KB Output is correct
9 Correct 218 ms 8580 KB Output is correct
10 Correct 593 ms 22748 KB Output is correct
11 Correct 302 ms 23372 KB Output is correct
12 Correct 288 ms 21732 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 144 ms 13936 KB Output is correct
15 Correct 42 ms 2512 KB Output is correct
16 Correct 799 ms 22780 KB Output is correct
17 Correct 296 ms 22172 KB Output is correct
18 Correct 329 ms 22180 KB Output is correct

Subtask #4
39.0 / 39.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 2 ms 340 KB Output is correct
4 Correct 8 ms 980 KB Output is correct
5 Correct 5 ms 1080 KB Output is correct
6 Correct 6 ms 1080 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 146 ms 14024 KB Output is correct
9 Correct 210 ms 8552 KB Output is correct
10 Correct 592 ms 22768 KB Output is correct
11 Correct 298 ms 23308 KB Output is correct
12 Correct 298 ms 21732 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 139 ms 13868 KB Output is correct
15 Correct 46 ms 2516 KB Output is correct
16 Correct 789 ms 22684 KB Output is correct
17 Correct 317 ms 22280 KB Output is correct
18 Correct 296 ms 22172 KB Output is correct
19 Correct 731 ms 100256 KB Output is correct
20 Correct 738 ms 100252 KB Output is correct
21 Correct 705 ms 100252 KB Output is correct
22 Correct 742 ms 100212 KB Output is correct
23 Correct 730 ms 100252 KB Output is correct
24 Correct 712 ms 100228 KB Output is correct
25 Correct 718 ms 100252 KB Output is correct
26 Correct 719 ms 100252 KB Output is correct
27 Correct 728 ms 100332 KB Output is correct
28 Correct 695 ms 100276 KB Output is correct
29 Correct 685 ms 100256 KB Output is correct
30 Correct 681 ms 100264 KB Output is correct