oj.uz

Submission #858290

# Submission time Handle Problem Language Result Execution time Memory
858290 2023-10-08T02:44:58 Z Zian_Jacobson Growing Trees (BOI11_grow) C++17
100 / 100
 229 ms 4440 KB 
#include<bits/stdc++.h>
using namespace std;
#define cIO ios_base::sync_with_stdio(0);cin.tie(0)
#define fileIO(x) ifstream cin(string(x)+".in"); ofstream fout(string(x)+".out")
#define cont(container, object) (container.find(object)!=container.end())
#define sz(x) (int) (x).size()
#define ll long long
#define v vector
struct FenTree
{
	int N;
	//1-based indexing
	vector<int> fenwick, arr;
	FenTree(int siz)
	{
		N = siz;
		fenwick.resize(N + 1, 0);
		arr.resize(N + 1, 0);
		return;
	}
	FenTree()
	{

	}
	int len(int pos)//returns length of Fenwick segment ending at position pos. Equal to greatest power of 2 that divides it.
	{
		return pos & -pos;
	}
	void update(int pos, int val)//add new_val to arr[pos] and updates the Fenwick Tree
	{

		arr[pos] += val;
		while (pos <= N)
		{
			fenwick[pos] += val;
			pos += len(pos); //steps to minimum next interval that contains the interval defined by pos
		}
	}
	int query(int pos)//sum from arr[1]..arr[pos]
	{
		int ans = 0;
		while (pos > 0)
		{
			ans += fenwick[pos];
			pos -= len(pos);
		}
		return ans;
	}
};
struct FenTreeRURQ //1-indexed, since 0 is used for sum
{
	int N;
	FenTree b1, b2;//b: difference array (prefix sum -> original), ib=i*bf
	FenTreeRURQ(int siz)
	{
		N = siz;
		b1 = FenTree(siz + 2), b2 = FenTree(siz + 2);
	}
	void update(int l, int r, int val)//add val to the interval
	{
		b1.update(l, val); b1.update(r + 1, -val);
		b2.update(l, l * val); b2.update(r + 1, -(r + 1) * val);
	}
	int query(int l, int r)//sum from l to r, l should be >=1
	{
		int lsub = (l)*b1.query(l - 1) - b2.query(l - 1);
		int rsub = (r + 1) * b1.query(r) - b2.query(r);
		return rsub - lsub;
	}
	int get(int pos)//value at pos, 4x faster
	{
		return b1.query(pos);
	}
};
int main()
{
	//fileIO("trees"); 
	int N, M; cin >> N >> M;
	v<int> h(N);
	for (int i = 0; i <= N - 1; i++) cin >> h[i];
	sort(h.begin(), h.end());
	FenTreeRURQ tree(N);
	for (int i = 0; i <= N - 1; i++) tree.update(i+1, i+1, h[i]);
	for (int z = 0; z <= M - 1; z++)
	{
		char state; cin >> state;
		if (state == 'F')//fertilize, update
		{
			int c, h; cin >> c >> h;
			if (tree.get(N) < h) continue; //nothing to update
			//find least value >=h
			int low_first, high_first, low_second, high_second;//two intervals
			{//find low_first
				int low = 1, high = N;
				while (low != high)
				{
					int mid = (low + high) / 2;
					if (tree.get(mid) >= h) high = mid;
					else low = mid + 1;
				}
				low_first = low;
			}
			if (low_first + c - 1 >= N)//not enough trees
			{
				tree.update(low_first, N, 1);
				continue;
			}
			int h_end = tree.get(low_first + c - 1);
			{//find high_first
				int low = 1, high = N;
				while (low != high)
				{
					int mid = (low + high) / 2;
					if (tree.get(mid) >= h_end) high = mid;
					else low = mid + 1;
				}
				high_first = low;
			}
			{//find high_second
				int low = 1, high = N;
				while (low != high)
				{
					int mid = (low + high + 1) / 2;
					if (tree.get(mid) <= h_end) low = mid;
					else high = mid-1;
				}
				high_second = low;
			}
			low_second = high_second + high_first - (low_first + c - 1);
			tree.update(low_first, high_first - 1, 1);
			tree.update(low_second, high_second, 1);
			//debug
			//for (int i = 1; i <= N; i++) cerr << tree.get(i) << " ";
			//cerr << "\n";
		}
		else if (state == 'C')//query
		{
			int _min, _max; cin >> _min >> _max;
			if (_min > tree.get(N) || _max < tree.get(1))
			{
				cout << "0\n";
				continue;
			}
			int min_begin, max_end;
			{//find low_first
				int low = 1, high = N;
				while (low != high)
				{
					int mid = (low + high) / 2;
					if (tree.get(mid) >= _min) high = mid;
					else low = mid + 1;
				}
				min_begin = low;
			}
			{//find high_second
				int low = 1, high = N;
				while (low != high)
				{
					int mid = (low + high + 1) / 2;
					if (tree.get(mid) <= _max) low = mid;
					else high = mid - 1;
				}
				max_end = low;
			}
			cout << max_end - min_begin + 1 << "\n";
		}
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 3424 KB Output is correct
2 Correct 193 ms 3640 KB Output is correct
3 Correct 74 ms 3756 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 6 ms 348 KB Output is correct
3 Correct 7 ms 348 KB Output is correct
4 Correct 7 ms 612 KB Output is correct
5 Correct 135 ms 1364 KB Output is correct
6 Correct 171 ms 1616 KB Output is correct
7 Correct 7 ms 600 KB Output is correct
8 Correct 119 ms 1256 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 1844 KB Output is correct
2 Correct 164 ms 1904 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 136 ms 1456 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 1852 KB Output is correct
2 Correct 178 ms 1656 KB Output is correct
3 Correct 8 ms 604 KB Output is correct
4 Correct 170 ms 1768 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 2640 KB Output is correct
2 Correct 163 ms 3152 KB Output is correct
3 Correct 42 ms 1116 KB Output is correct
4 Correct 66 ms 3412 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 2900 KB Output is correct
2 Correct 166 ms 3412 KB Output is correct
3 Correct 72 ms 3412 KB Output is correct
4 Correct 47 ms 1268 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 3060 KB Output is correct
2 Correct 127 ms 3416 KB Output is correct
3 Correct 75 ms 3720 KB Output is correct
4 Correct 41 ms 1116 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 3796 KB Output is correct
2 Correct 163 ms 3104 KB Output is correct
3 Correct 46 ms 2896 KB Output is correct
4 Correct 123 ms 3152 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 3544 KB Output is correct
2 Correct 182 ms 3828 KB Output is correct
3 Correct 139 ms 4028 KB Output is correct

Subtask #10
10.0 / 10.0

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