Submission #1213423

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213423		orzorzorz	Growing Trees (BOI11_grow)	C++20	100 / 100	79 ms	1604 KiB

grow

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000;

int n, q;
int bit[MAXN + 10];

void add(int l, int r, int x) {
    if (l > r) return;
    for (int i = l; i < n; i |= i + 1) 
        bit[i] += x;
    for (int i = r + 1; i < n; i |= i + 1)
        bit[i] -= x;
}

int query(int i) {
    int res = 0;
    for (; i >= 0; i = (i & (i + 1)) - 1)
        res += bit[i];
    return res;
}

template<class T, class F>
T firstTrue(T lo, T hi, F f) {
    ++hi;
    while (lo < hi) {
        T mid = lo + (hi - lo) / 2;
        if (f(mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

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

    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) 
        cin >> a[i];
    sort(a.begin(), a.end());
    memset(bit, 0, sizeof(bit));
    for (int i = 0; i < n; ++i) {
        add(i, i, a[i]);
    }

    for (int i = 0; i < q; ++i) {
        char ty;
        int x, y;
        cin >> ty >> x >> y;
        if (ty == 'F') {
            int c = x, h = y;
            int l = firstTrue(0, n - 1, [&](int idx) { return query(idx) >= h; });
            if (l == n) 
                continue;
            int r0 = l + c - 1;
            if (r0 >= n - 1) {
                add(l, n - 1, 1);
            } else {
                int x_val = query(r0);
                int l_ = firstTrue(l, n - 1, [&](int idx) { return query(idx) >= x_val; });
                int r_ = firstTrue(l_, n - 1, [&](int idx) { return query(idx) > x_val; }) - 1;
                int cnt_first = l_ - l;
                int rem = c - cnt_first;
                if (cnt_first > 0) {
                    add(l, l_ - 1, 1);
                }
                if (rem > 0) {
                    int start = r_ - rem + 1;
                    int end = r_;
                    add(start, end, 1);
                }
            }
        } else {
            int min_val = x, max_val = y;
            int l_index = firstTrue(0, n - 1, [&](int idx) { return query(idx) >= min_val; });
            int r_index = firstTrue(0, n - 1, [&](int idx) { return query(idx) > max_val; });
            cout << (r_index - l_index) << '\n';
        }
    }
    return 0;
}

• 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