Submission #1267454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267454		uranium235	Growing Trees (BOI11_grow)	C++17	100 / 100	88 ms	6728 KiB

grow

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const char nn = '\n';

struct state {
    int sum = 0, lastZero = -1, firstZero = INT32_MAX;
    void set(int i, int x) {
        sum = x;
        lastZero = (x == 0) ? -1 : i;
        firstZero = (x == 0) ? INT32_MAX : i;
    }
    void merge(state &l, state &r) {
        sum = l.sum + r.sum;
        lastZero = max(l.lastZero, r.lastZero);
        firstZero = min(l.firstZero, r.firstZero);
    }
};

class segtree {
    public:
        int n;
        vector<state> a;
        segtree(int n, const vector<state> &arr) : n(n), a(4 * n) {
            build(0, n - 1, 1, arr);
        }
        void build(int l, int r, int v, const vector<state> &arr) {
            if (l == r) a[v] = arr[l];
            else {
                int m = (l + r) / 2;
                build(l, m, 2 * v, arr);
                build(m + 1, r, 2 * v + 1, arr);
                a[v].merge(a[2 * v], a[2 * v + 1]);
            }
        }
        void upd(int i, int x, int l, int r, int v) {
            if (l == r) a[v].set(i, a[v].sum + x);
            else {
                int m = (l + r) / 2;
                if (i <= m) upd(i, x, l, m, 2 * v);
                else upd(i, x, m + 1, r, 2 * v + 1);
                a[v].merge(a[2 * v], a[2 * v + 1]);
            }
        }
        void upd(int i, int x) {upd(i, x, 0, n - 1, 1);}
        int pref(int x, int l, int r, int v) {
            if (a[v].sum < x) return n;
            else if (l == r) return l;
            else {
                int m = (l + r) / 2;
                if (a[2 * v].sum < x) return pref(x - a[2 * v].sum, m + 1, r, 2 * v + 1);
                else return pref(x, l, m, 2 * v);
            }
        }
        int pref(int x) {return pref(x, 0, n - 1, 1);}
        void qry(int ll, int rr, int l, int r, int v, state& x) {
            if (r < ll || rr < l) return;
            else if (ll <= l && r <= rr) x.merge(x, a[v]);
            else {
                int m = (l + r) / 2;
                qry(ll, rr, l, m, 2 * v, x);
                qry(ll, rr, m + 1, r, 2 * v + 1, x);
            }
        }
        void qry(int ll, int rr, state &x) {qry(ll, rr, 0, n - 1, 1, x);}
        state get(int i, int l, int r, int v) {
            if (l == r) return a[v];
            else {
                int m = (l + r) / 2;
                if (i <= m) return get(i, l, m, 2 * v);
                else return get(i, m + 1, r, 2 * v + 1);
            }
        }
        void print() {
            int pref = 0;
            cout << "tree ";
            for (int i = 0; i < n; i++) {
                pref += get(i, 0, n - 1, 1).sum;
                cout << pref << " ";
            }
            cout << nn;
        }
};

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

    int n, m;
    cin >> n >> m;
    vector<state> a(n);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> a[i].sum;
    }
    sort(a.begin(), a.end(), [](const state &l, const state &r) {
        return l.sum < r.sum;
    });
    for (int i = n - 1; i >= 0; i--) {
        if (i > 0) a[i].sum -= a[i - 1].sum;
        a[i].set(i, a[i].sum);
    }

    segtree tree(n, a);
    // tree.print();
    // state dbg;
    // tree.qry(0, 0, dbg);
    // cout << "dbg " << dbg.lastZero << tree.get(0, 0, n - 1, 1).lastZero << nn;
    for (int i = 0; i < m; i++) {
        char c;
        int a, b;
        cin >> c >> a >> b;
        if (c == 'C') {
            cout << (tree.pref(b + 1) - tree.pref(a)) << '\n';
        } else {
            // first plant eligible for fertilizer
            int first = tree.pref(b);
            if (first == n) continue;
            int upper = min(n - 1, first + a - 1);
            state higher, lower;
            tree.qry(upper + 1, n - 1, higher);
            higher.firstZero = min(higher.firstZero, n);
            tree.qry(0, upper, lower);

            int moved = upper - lower.lastZero + 1;

            if (higher.firstZero < n) {
                tree.upd(higher.firstZero, -1);
            }
            tree.upd(higher.firstZero - moved, 1);
            tree.upd(first, 1);
            tree.upd(lower.lastZero, -1);

            // cout << "f " << lower.lastZero << " " << higher.firstZero << " " << moved << " " << upper << nn;
            // tree.print();
        }
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10