oj.uz

Submission #660277

# Submission time Handle Problem Language Result Execution time Memory
660277 2022-11-21T13:01:18 Z franfill Growing Trees (BOI11_grow) C++17
100 / 100
 456 ms 4520 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 2952 KB Output is correct
2 Correct 310 ms 4448 KB Output is correct
3 Correct 111 ms 4332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 6 ms 340 KB Output is correct
3 Correct 8 ms 340 KB Output is correct
4 Correct 5 ms 368 KB Output is correct
5 Correct 153 ms 1524 KB Output is correct
6 Correct 199 ms 1872 KB Output is correct
7 Correct 12 ms 564 KB Output is correct
8 Correct 134 ms 1144 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 780 KB Output is correct
2 Correct 202 ms 2048 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 154 ms 1324 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 900 KB Output is correct
2 Correct 200 ms 1940 KB Output is correct
3 Correct 23 ms 564 KB Output is correct
4 Correct 186 ms 1892 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 1748 KB Output is correct
2 Correct 276 ms 4016 KB Output is correct
3 Correct 45 ms 1344 KB Output is correct
4 Correct 102 ms 3988 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 2900 KB Output is correct
2 Correct 267 ms 4096 KB Output is correct
3 Correct 110 ms 4244 KB Output is correct
4 Correct 45 ms 1324 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 2928 KB Output is correct
2 Correct 183 ms 4252 KB Output is correct
3 Correct 112 ms 4368 KB Output is correct
4 Correct 44 ms 1236 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 3028 KB Output is correct
2 Correct 255 ms 3928 KB Output is correct
3 Correct 68 ms 3816 KB Output is correct
4 Correct 162 ms 3872 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 2944 KB Output is correct
2 Correct 307 ms 4348 KB Output is correct
3 Correct 456 ms 4520 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 3152 KB Output is correct