oj.uz

Submission #640888

# Submission time Handle Problem Language Result Execution time Memory
640888 2022-09-15T13:35:20 Z Sharky Wall (IOI14_wall) C++17
100 / 100
 734 ms 91724 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, 1, size);
    }
    // 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, 1, size);
    }
};

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

#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+1, r+1, h);
    }
    st.calc();
    for (int i = 1; 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 2 ms 340 KB Output is correct
4 Correct 8 ms 1084 KB Output is correct
5 Correct 6 ms 980 KB Output is correct
6 Correct 5 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 122 ms 8316 KB Output is correct
3 Correct 205 ms 4896 KB Output is correct
4 Correct 560 ms 15136 KB Output is correct
5 Correct 269 ms 15024 KB Output is correct
6 Correct 266 ms 15016 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 440 KB Output is correct
3 Correct 2 ms 316 KB Output is correct
4 Correct 8 ms 1012 KB Output is correct
5 Correct 6 ms 980 KB Output is correct
6 Correct 5 ms 980 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 121 ms 10028 KB Output is correct
9 Correct 201 ms 6584 KB Output is correct
10 Correct 587 ms 14992 KB Output is correct
11 Correct 279 ms 15064 KB Output is correct
12 Correct 268 ms 15068 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 125 ms 9980 KB Output is correct
15 Correct 43 ms 2524 KB Output is correct
16 Correct 733 ms 15004 KB Output is correct
17 Correct 277 ms 15072 KB Output is correct
18 Correct 277 ms 15044 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 356 KB Output is correct
4 Correct 8 ms 980 KB Output is correct
5 Correct 5 ms 1012 KB Output is correct
6 Correct 5 ms 980 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 123 ms 9980 KB Output is correct
9 Correct 202 ms 6624 KB Output is correct
10 Correct 571 ms 15072 KB Output is correct
11 Correct 276 ms 15068 KB Output is correct
12 Correct 267 ms 15236 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 123 ms 9980 KB Output is correct
15 Correct 41 ms 2516 KB Output is correct
16 Correct 734 ms 15116 KB Output is correct
17 Correct 274 ms 15032 KB Output is correct
18 Correct 283 ms 15112 KB Output is correct
19 Correct 679 ms 91616 KB Output is correct
20 Correct 665 ms 91724 KB Output is correct
21 Correct 679 ms 91596 KB Output is correct
22 Correct 663 ms 91536 KB Output is correct
23 Correct 663 ms 91380 KB Output is correct
24 Correct 670 ms 91236 KB Output is correct
25 Correct 678 ms 90964 KB Output is correct
26 Correct 674 ms 90960 KB Output is correct
27 Correct 669 ms 90560 KB Output is correct
28 Correct 679 ms 90516 KB Output is correct
29 Correct 665 ms 90336 KB Output is correct
30 Correct 667 ms 90080 KB Output is correct