oj.uz

Submission #333148

# Submission time Handle Problem Language Result Execution time Memory
333148 2020-12-04T19:33:52 Z smax Growing Trees (BOI11_grow) C++17
100 / 100
 178 ms 10732 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__);
#else
#define DEBUG(...) 6;
#endif

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
template<typename T> void debug(string s, T x) {cerr << s << " = " << x << "\n";}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {cerr << s.substr(0, s.find(',')) << " = " << x << " | "; debug(s.substr(s.find(',') + 2), args...);}

struct Node {
    int mx, cnt, lazy = 0, l, r;

    void leaf(int val) {
        mx = val;
        cnt = 1;
    }

    void pull(Node &a, Node &b) {
        mx = max(a.mx, b.mx);
        cnt = a.cnt + b.cnt;
    }

    void push(int val) {
        lazy += val;
    }

    void apply() {
        mx += lazy;
        lazy = 0;
    }
};

struct SegmentTree {
    int n;
    vector<int> a;
    vector<Node> st;

    SegmentTree(int _n) : n(_n), st(4*n) {
        build(1, 0, n-1);
    }

    SegmentTree(const vector<int> &_a) : n(_a.size()), a(_a), st(4*n) {
        build(1, 0, n-1);
    }

    void build(int p, int l, int r) {
        st[p].l = l;
        st[p].r = r;
        if (l == r) {
            st[p].leaf(a[l]);
            return;
        }

        int m = (l + r) / 2;
        build(2*p, l, m);
        build(2*p+1, m+1, r);
        st[p].pull(st[2*p], st[2*p+1]);
    }

    void push(int p) {
        if (st[p].lazy) {
            if (st[p].l != st[p].r) {
                st[2*p].push(st[p].lazy);
                st[2*p+1].push(st[p].lazy);
            }
            st[p].apply();
        }
    }

    Node query(int p, int i, int j) {
        push(p);

        if (st[p].l == i && st[p].r == j)
            return st[p];

        int m = (st[p].l + st[p].r) / 2;
        if (j <= m)
            return query(2*p, i, j);
        else if (i > m)
            return query(2*p+1, i, j);
        Node ret, ls = query(2*p, i, m), rs = query(2*p+1, m+1, j);
        ret.pull(ls, rs);
        return ret;
    }

    int query(int i, int j) {
        return query(1, i, j).mx;
    }

    void update(int p, int i, int j, int val) {
        if (st[p].l == i && st[p].r == j) {
            st[p].push(val);
            push(p);
            return;
        }

        push(p);

        int m = (st[p].l + st[p].r) / 2;
        if (j <= m) {
            update(2*p, i, j, val);
            push(2*p+1);
        } else if (i > m) {
            push(2*p);
            update(2*p+1, i, j, val);
        } else {
            update(2*p, i, m, val);
            update(2*p+1, m+1, j, val);
        }
        st[p].pull(st[2*p], st[2*p+1]);
    }

    void update(int i, int j, int val) {
        if (i > j) return;
        update(1, i, j, val);
    }

    int leftMost(int p, int h) {
        if (st[p].l == st[p].r) {
            if (st[p].mx < h)
                return st[p].l + 1;
            return st[p].l;
        }
        push(2*p);
        push(2*p+1);
        if (st[2*p].mx >= h)
            return leftMost(2*p, h);
        return leftMost(2*p+1, h);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i=0; i<n; i++)
        cin >> a[i];

    sort(a.begin(), a.end());
    SegmentTree st(a);
    for (int i=0; i<m; i++) {
        char t;
        cin >> t;
        if (t == 'F') {
            int c, h;
            cin >> c >> h;
            int l = st.leftMost(1, h);
            if (l + c - 1 < n - 1) {
                int finalValue = st.query(l + c - 1, l + c - 1), nextToFinal = st.query(l + c, l + c);
                if (finalValue == nextToFinal) {
                    // to maintain sorted array, instead update separate range
                    int firstOfFinal = st.leftMost(1, finalValue), firstNotFinal = st.leftMost(1, finalValue + 1);
                    int sz = l + c - firstOfFinal;
                    assert(firstOfFinal - l + sz == c);
                    st.update(l, firstOfFinal - 1, 1);
                    st.update(firstNotFinal - sz, firstNotFinal - 1, 1);
                } else {
                    st.update(l, min(l + c - 1, n - 1), 1);
                }
            } else {
                st.update(l, min(l + c - 1, n - 1), 1);
            }
        } else {
            int mn, mx;
            cin >> mn >> mx;
            int l = st.leftMost(1, mn), r = st.leftMost(1, mx + 1);
            cout << r - l << "\n";
        }
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 8172 KB Output is correct
2 Correct 128 ms 9452 KB Output is correct
3 Correct 62 ms 9196 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 42 ms 1900 KB Output is correct
6 Correct 52 ms 2028 KB Output is correct
7 Correct 5 ms 876 KB Output is correct
8 Correct 35 ms 1644 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1388 KB Output is correct
2 Correct 54 ms 2412 KB Output is correct
3 Correct 2 ms 1004 KB Output is correct
4 Correct 40 ms 1900 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 1516 KB Output is correct
2 Correct 57 ms 2284 KB Output is correct
3 Correct 10 ms 1004 KB Output is correct
4 Correct 53 ms 2412 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 6124 KB Output is correct
2 Correct 123 ms 8044 KB Output is correct
3 Correct 16 ms 2284 KB Output is correct
4 Correct 50 ms 7916 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 6892 KB Output is correct
2 Correct 124 ms 8556 KB Output is correct
3 Correct 64 ms 8192 KB Output is correct
4 Correct 16 ms 2284 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 7424 KB Output is correct
2 Correct 97 ms 9324 KB Output is correct
3 Correct 60 ms 8940 KB Output is correct
4 Correct 15 ms 2284 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 7916 KB Output is correct
2 Correct 126 ms 8300 KB Output is correct
3 Correct 43 ms 9836 KB Output is correct
4 Correct 88 ms 9324 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 8020 KB Output is correct
2 Correct 113 ms 9580 KB Output is correct
3 Correct 178 ms 10732 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 9324 KB Output is correct