제출 #1254435

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254435		XXBabaProBerkay	Growing Trees (BOI11_grow)	C++20	100 / 100	145 ms	5956 KiB

grow

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

#define F first
#define S second
#define MP make_pair
#define PB push_back

using ll = long long;
using ld = long double;
using pi = pair<int, int>;
using pll = pair<ll, ll>;

template<typename T>
using vec = vector<T>;

template<typename T, int N>
using arr = array<T, N>;

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }

const ll INF = 1e18;
const int MOD = 998244353;

int N, M;
vec<int> h, t_min, t_max, lazy;

void build(int l = 1, int r = N, int k = 1)
{
	if (l == r)
	{
		t_min[k] = t_max[k] = h[l];
		return;
	}

	int m = (l + r) / 2;

	build(l, m, k * 2);
	build(m + 1, r, k * 2 + 1);

	t_max[k] = max(t_max[k * 2], t_max[k * 2 + 1]);
	t_min[k] = min(t_min[k * 2], t_min[k * 2 + 1]);
}

void push(int k)
{
	t_min[k * 2] += lazy[k];
	t_min[k * 2 + 1] += lazy[k];

	t_max[k * 2] += lazy[k];
	t_max[k * 2 + 1] += lazy[k];

	lazy[k * 2] += lazy[k];
	lazy[k * 2 + 1] += lazy[k];

	lazy[k] = 0;
}

void update(int ql, int qr, int l = 1, int r = N, int k = 1)
{
	if (l > qr || r < ql) return;
	if (l >= ql && r <= qr)
	{
		t_min[k]++;
		t_max[k]++;
		lazy[k]++;
		return;
	}

	push(k);

	int m = (l + r) / 2;

	update(ql, qr, l, m, k * 2);
	update(ql, qr, m + 1, r, k * 2 + 1);

	t_max[k] = max(t_max[k * 2], t_max[k * 2 + 1]);
	t_min[k] = min(t_min[k * 2], t_min[k * 2 + 1]);
}

int query1(int x, bool lr, int l = 1, int r = N, int k = 1)
{
	if (l == r)
	{
		if (lr == 0) return (t_max[k] >= x ? l : -1);
		else return (t_min[k] <= x ? r : -1);
	}
	push(k);
	int m = (l + r) / 2;

	if (lr == 0)
	{
		if (t_max[k * 2] >= x)
			return query1(x, lr, l, m, k * 2);
		else return query1(x, lr, m + 1, r, k * 2 + 1);
	}
	else {
		if (t_min[k * 2 + 1] <= x)
			return query1(x, lr, m + 1, r, k * 2 + 1);
		else return query1(x, lr, l, m, k * 2);
	}
}

int query2(int p, int l = 1, int r = N, int k = 1)
{
	if (l > p || r < p) return -1;
	if (l == r && r == p) return t_min[k];
	push(k);
	int m = (l + r) / 2;
	int a = query2(p, l, m, k * 2);
	int b = query2(p, m + 1, r, k * 2 + 1);

	return (a == -1 ? b : a);
}

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

	cin >> N >> M;
	h = vec<int>(N + 1);
	t_min = t_max = lazy = vec<int>(N << 2);
	for (int i = 1; i <= N; i++)
		cin >> h[i];

	sort(h.begin() + 1, h.end());

	build();

	while (M--)
	{
		char q;
		cin >> q;
		
		if (q == 'F')
		{
			int c, H;
			cin >> c >> H;
			int l1 = query1(H, 0);
			if (l1 == -1) continue;

			int x = query2(min(N, l1 + c - 1));
			int r1 = query1(x, 0) - 1;
			int r2 = query1(x, 1);
			int l2 = r2 - (min(N, l1 + c - 1) - r1) + 1;

			if (l1 <= r1) update(l1, r1);
			if (l2 <= r2) update(l2, r2);
		}
		else
		{
			int mn, mx;
			cin >> mn >> mx;
			int l = query1(mn, 0);
			int r = query1(mx, 1);
			if (l == -1 || r == -1)
				cout << "0\n";
			else cout << r - l + 1 << '\n';
		}
	}
}

• 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