Submission #889920

#	Time	Username	Problem	Language	Result	Execution time	Memory
889920		chanhchuong123	Growing Trees (BOI11_grow)	C++14	100 / 100	53 ms	3496 KiB

grow

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

#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {
	return uniform_int_distribution<int>(l, r)(rng);
}

const int MAX = 100010;
int nArr;
int nQuery;
int h[MAX];
int bit[MAX];

void update(int id, int delta) {
    for (; id <= nArr; id += id & -id)
        bit[id] += delta;
}

void update(int l, int r, int delta) {
    update(l, +delta);
    update(r + 1, -delta);
}

int getHigh(int id) {
    int res = 0;
    for (; id > 0; id -= id & -id)
        res += bit[id];
    return  res;
}

int getFirst(int high) { // find first pos that h[pos] >= high
    int pos = 0;
    for (int j = 16; j >= 0; --j) {
        if (pos + (1 << j) > nArr) continue;
        if (bit[pos + (1 << j)] < high) {
            pos += 1 << j;
            high -= bit[pos];
        }
    }
    return pos + 1;
}

int getLast(int high) { // find last pos that h[pos] <= high
    int pos = 0;
    for (int j = 16; j >= 0; --j) {
        if (pos + (1 << j) > nArr) continue;
        if (bit[pos + (1 << j)] <= high) {
            pos += 1 << j;
            high -= bit[pos];
        }
    }
    return pos;
}

void process(void) {
    cin >> nArr >> nQuery; for (int i = 1; i <= nArr; ++i) cin >> h[i];
    sort(h + 1, h + 1 + nArr);

    for (int i = 1; i <= nArr; ++i) {
        update(i, h[i] - h[i - 1]);
    }
    while (nQuery--) {
        char o; int l, r; cin >> o >> l >> r;

        if (o == 'F') {
            int L = getFirst(r), R = min(nArr, L + l - 1);
            if (L <= nArr) {
                if (R == nArr) update(L, +1);
                else {
                    int maxHigh = getHigh(R), lastL = getFirst(maxHigh), lastR = getLast(maxHigh);
                    update(L, lastL - 1, +1); l -= lastL - L;
                    update(lastR - l + 1, lastR, +1);
                }
            }
            continue;
        }

        cout << max(0, getLast(r) - getFirst(l) + 1) << '\n';
    }
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    process();
	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