Submission #660277

#	Time	Username	Problem	Language	Result	Execution time	Memory
660277		franfill	Growing Trees (BOI11_grow)	C++17	100 / 100	456 ms	4520 KiB

grow

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

struct segtree
{
	struct node
	{
		int max;
		int lazy = 0;
		node(int v) : max(v)
		{
		}
		node() : max(-1)
		{
		}
	};

	void merge(node &c, node a, node b)
	{
		c.max = max(a.max, b.max);
	}
	int n;
	int w;
	vector < node > T;

	segtree(vector < int > V)
	{
		w = V.size();
		for (n = 1; n < V.size(); n *= 2);
		T.resize(n*2);
		for (int i = 0; i < V.size(); i++)
			T[n+i] = node(V[i]);
		for (int k = n-1; k; k--)
			merge(T[k], T[k*2], T[k*2+1]);
	}

	void propagate(int k)
	{
		T[k].max += T[k].lazy;
		if (k < n)
		{
			T[k*2].lazy += T[k].lazy;
			T[k*2+1].lazy += T[k].lazy;
		}
		T[k].lazy = 0;
	}

	void add(int l, int r, int k=1, int x=0, int y=-1)
	{
		if (y == -1)
			y = n;
		if (l <= x && y <= r)
			T[k].lazy++;
		propagate(k);
		if (l <= x && y <= r)
			return;
		if (r <= x || y <= l)
			return;
		int m = (x+y)/2;
		add(l, r, k*2, x, m);
		add(l, r, k*2+1, m, y);
		merge(T[k], T[k*2], T[k*2+1]);
	}

	int right_bound(int l, int r, int h, int k=1, int x=0, int y=-1)
	{
		if (y == -1)
			y = n;
		propagate(k);
		if (r <= x || y <= l)
			return w;
		if (T[k].max < h)
			return w;
		if (x == y-1)
			return x;
		int m = (x+y)/2;
		int ans = right_bound(l, r, h, k*2, x, m);
		if (ans == w)
			ans = right_bound(l, r, h, k*2+1, m, y);
		return ans;
	}
};

int main()
{
	int N, M;	
	cin >> N >> M;
	vector < int > H(N);
	for (int &h : H)
		cin >> h;
	sort(H.begin(), H.end());
	segtree seg(H);
	for (int m = 0; m < M; m++)
	{
		char t;
		cin >> t;
		if (t == 'F')
		{
			int c, h;
			cin>> c >> h;
			int i = seg.right_bound(0, N, h);
			if (c >= N-i)
			{
				seg.add(i, N);
				continue;
			}
			int l = h, r = (M+N)+1;
			while(l < r-1)
			{
				int m = (l+r)/2;
				int j = seg.right_bound(i, N, m);
				if ((j-i) <= c)
					l = m;
				else
					r = m;
			}
			int j1 = seg.right_bound(i, N, l);
			int j2 = seg.right_bound(i, N, r);
			int leftover = c - (j1 - i);
			seg.add(i, j1);
			seg.add(j2-leftover, j2);
		}
		else
		{
			int mi, ma;
			cin >> mi >> ma;
			int i = seg.right_bound(0, N, mi);
			int j = seg.right_bound(0, N, ma+1);
			cout << j-i << "\n";
		}
	}
}

Compilation message (stderr)

grow.cpp: In constructor 'segtree::segtree(std::vector<int>)':
grow.cpp:29:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for (n = 1; n < V.size(); n *= 2);
      |               ~~^~~~~~~~~~
grow.cpp:31:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for (int i = 0; i < V.size(); i++)
      |                   ~~^~~~~~~~~~

• 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