Submission #1235357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235357		ssitaram	Growing Trees (BOI11_grow)	C++20	100 / 100	73 ms	1604 KiB

grow

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

typedef long long ll;
typedef long double ld;

struct BIT {
	int n;
	vector<int> T;

	BIT(int sz) : n(sz), T(n + 1) {}

	void inc(int i, int v) {
		++i;
		for (; i <= n; i += i & -i) {
			T[i] += v;
		}
	}

	void incr(int a, int b) {
		if (a > b) return;
		inc(a, 1);
		inc(b + 1, -1);
	}

	int val(int i) {
		++i;
		int res = 0;
		for (; i > 0; i -= i & -i) {
			res += T[i];
		}
		return res;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m; cin >> n >> m;
	vector<int> a(n);
	for (int& i : a) cin >> i;
	sort(a.begin(), a.end());
	BIT bit(n);
	bit.inc(0, a[0]);
	for (int i = 1; i < n; ++i) {
		bit.inc(i, a[i] - a[i - 1]);
	}
	auto first = [&bit](int k) {
		int lo = 0, hi = bit.n;
		while (lo < hi) {
			int m = (lo + hi) / 2;
			if (bit.val(m) >= k) {
				hi = m;
			} else {
				lo = m + 1;
			}
		}
		return lo;
	};
	while (m--) {
		char tp; cin >> tp;
		if (tp == 'F') {
			int c, h; cin >> c >> h;
			int st = first(h);
			int en = st + c - 1;
			if (en >= n) {
				bit.incr(st, n - 1);
			} else {
				int a = max(first(bit.val(en)), st);
				int b = first(bit.val(en) + 1) - 1;
				bit.incr(st, a - 1);
				int cnt = en - a + 1;
				bit.incr(b - cnt + 1, b);
			}
		} else {
			int mi, ma; cin >> mi >> ma;
			cout << (first(ma + 1) - 1) - (first(mi) - 1) << '\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