Submission #858290

#	Time	Username	Problem	Language	Result	Execution time	Memory
858290		Zian_Jacobson	Growing Trees (BOI11_grow)	C++17	100 / 100	229 ms	4440 KiB

grow

#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 / 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