Submission #1265914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265914		canhnam357	Growing Trees (BOI11_grow)	C++20	100 / 100	92 ms	3144 KiB

grow

// source problem : 
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define lb lower_bound
#define ub upper_bound
#define MASK(i) (1LL << (i))
void ckmax(int& f, int s)
{
	f = (f > s ? f : s);
}
void ckmin(int& f, int s)
{
	f = (f < s ? f : s);
}
const int inf = 2e9;
int st[1 << 18] = {}, lz[1 << 18] = {}, a[1 << 17], n;
void build(int id = 1, int l = 1, int r = 1 << 17)
{
	if (l == r)
	{
		if (l <= n) st[id] = a[l];
		else st[id] = inf;
		return;
	}
	int mid = (l + r) >> 1;
	build(id << 1, l, mid);
	build(id << 1 | 1, mid + 1, r);
	st[id] = max(st[id << 1], st[id << 1 | 1]);
}
void down(int id)
{
	if (!lz[id]) return;
	for (int i : {id << 1, id << 1 | 1})
	{
		st[i] += lz[id];
		lz[i] += lz[id];
	}
	lz[id] = 0;
}
void update(int u, int v, int x, int id = 1, int l = 1, int r = 1 << 17)
{
	if (r < u || l > v) return;
	if (l >= u && r <= v)
	{
		st[id] += x;
		lz[id] += x;
		return;
	}
	down(id);
	int mid = (l + r) >> 1;
	update(u, v, x, id << 1, l, mid);
	update(u, v, x, id << 1 | 1, mid + 1, r);
	st[id] = max(st[id << 1], st[id << 1 | 1]);
}
int find_first(int x, int id = 1, int l = 1, int r = 1 << 17)
{
	if (l == r) return l;
	down(id);
	int mid = (l + r) >> 1;
	if (st[id << 1] >= x) return find_first(x, id << 1, l, mid);
	return find_first(x, id << 1 | 1, mid + 1, r);
}
int get(int pos, int id = 1, int l = 1, int r = 1 << 17)
{
	if (l == r) return st[id];
	down(id);
	int mid = (l + r) >> 1;
	if (pos <= mid) return get(pos, id << 1, l, mid);
	return get(pos, id << 1 | 1, mid + 1, r);
}
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort(a + 1, a + n + 1);
	build();
	while (q--)
	{
		char c;
		int l, r;
		cin >> c >> l >> r;
		if (c == 'C') cout << find_first(r + 1) - find_first(l) << '\n';
		else
		{
			int p = find_first(r);
			if (n - p + 1 <= l) update(p, n, 1);
			else
			{
				int k = get(p + l - 1);
				int pp = find_first(k + 1) - 1;
				int ppp = find_first(k) - 1;
				update(p, ppp, 1);
				l -= ppp - p + 1;
				update(pp - l + 1, pp, 1);
			}
		}
	}
	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