Submission #1278716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278716		g4yuhg	Growing Trees (BOI11_grow)	C++20	100 / 100	547 ms	3864 KiB

grow

//Huyduocdithitp
#include<bits/stdc++.h>
typedef int ll;
#define endl '\n'
#define fi first
#define se second
#define pii pair<ll,ll>
#define N 100005
#define LOG 18
using namespace std;

const ll inf = 1e9;

// co doc sol
// nhan xet: khi ta tang 1, thu tu sort cua day a khong doi

// bai lon nay ma cung phai doc sol t that bai vl

bool ghuy4g;

ll n, m, a[N];

ll st[4 * N], f[4 * N];

void build(ll id, ll l, ll r) {
	if (l == r) {
		st[id] = a[l];
		return;
	}
	ll mid = (l + r) / 2;
	build(id * 2, l, mid);
	build(id * 2 + 1, mid + 1, r);
	st[id] = st[id * 2] + st[id * 2 + 1];
}

void lazy(ll id) {
	if (f[id] == 0) return;
	st[id] += f[id];
	if (id * 2 < 4 * N) {
		f[id * 2] += f[id];
	}
	if (id * 2 + 1 < 4 * N) {
		f[id * 2 + 1] += f[id];
	}
	f[id] = 0;
}

void update(ll id, ll l, ll r, ll L, ll R, ll v) {
	lazy(id);
	if (l > R || r < L) return;
	if (L <= l && r <= R) {
		f[id] += v;
		lazy(id);
		return;
	}
	ll mid = (l + r) / 2;
	update(id * 2, l, mid, L, R, v);
	update(id * 2 + 1, mid + 1, r, L, R, v);
	st[id] = st[id * 2] + st[id * 2 + 1];
}

ll get(ll id, ll l, ll r, ll i) {
	lazy(id);
	if (i > r || i < l) return 0;
	if (l == r) {
		return st[id];
	}
	ll mid = (l + r) /2;
	return get(id * 2, l, mid, i) + get(id * 2 + 1, mid + 1, r, i);
}

ll find(ll u) { // vi tri xa nhat ma co chieu cao <= u
	if (u == 0) return 0;
	ll l = 1, r = n, ans = 0;
	while (l <= r) {
		ll mid = (l + r) / 2;
		if (get(1, 1, n, mid) <= u) {
			ans = mid;
			l = mid + 1;
		}
		else {
			r = mid - 1;
		}
	}	
	return ans;
}

bool klinh;

signed main() {
	//freopen("test.inp", "r", stdin);
	//freopen("test.out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	sort(a + 1, a + 1 + n);
	
	build(1, 1, n);
	
	for (int i = 1; i <= m; i ++) {
		char tt;
		cin >> tt;
		if (tt == 'F') {
			ll c, h;
			cin >> c >> h;
			ll l = find(h - 1) + 1;
			ll r = min(l + c - 1, n);
			if (l > n) continue;
			// tim block cua r
			ll u = get(1, 1, n, r);
			ll bd = find(u - 1) + 1;
			ll kt = find(u);
			ll len = r - bd + 1;
			update(1, 1, n, l, bd - 1, 1);
			update(1, 1, n, kt - len + 1, kt, 1);
		}
		else {
			ll u, v;
			cin >> u>> v;
			cout << find(v) - find(u - 1) << endl;
		}
	}
		
	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
	
	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