Submission #394841

#	Time	Username	Problem	Language	Result	Execution time	Memory
394841		SavicS	Growing Trees (BOI11_grow)	C++14	100 / 100	115 ms	2028 KiB

grow

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 100005;
const int inf = 1e9 + 5;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

int n, q;
int niz[maxn];

ll dud[maxn];
void upd(int x, ll val) {
	while(x <= n) {
		dud[x] += val;
		x += x&(-x);
	}
}

ll query(int x) {
	ll sum = 0;
	while(x > 0) {
		sum += dud[x];
		x -= x&(-x);
	}
	return sum;
}

void add_range(int L, int R, int X) {
	upd(L, X);
	upd(R + 1, -X);
}

int main() 
{
	ios::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);
	cin >> n >> q;
	ff(i,1,n)cin >> niz[i];
	sort(niz + 1, niz + n + 1);

	ff(i,1,n)add_range(i, i, niz[i]);


	while(q--) {
		char tip;
		cin >> tip;

		if(tip == 'F') {
			int C, H;
			cin >> C >> H;

			int od = 0;
			{
				int l = 1, r = n, ans = n + 1;
				while(l <= r) {
					int mid = (l + r) / 2;
					if(query(mid) >= H) {
						ans = mid;
						r = mid - 1;
					} else l = mid + 1;
				}

				// od kog indeska su >= H
				od = ans;

			}

			if(od == n + 1)continue;

			int L = od, R = min(n, od + C - 1);
			if(R == n || query(R + 1) != query(R)) {
				add_range(L, R, 1);
				continue;
			}

			int first = 0;
			{
				int l = L, r = R, ans = 0;
				while(l <= r) {
					int mid = (l + r) / 2;
					if(query(mid) == query(R + 1)) {
						ans = mid;
						r = mid - 1;
					} else l = mid + 1;
				}

				first = ans;

			}
			int last = 0;
			{
				int l = first, r = n, ans = 0;
				while(l <= r) {
					int mid = (l + r) / 2;
					if(query(mid) == query(first)) {
						ans = mid;
						l = mid + 1;
					} else r = mid - 1;
				}

				last = ans;

			}

			add_range(L, first - 1, 1);
			int ost = R - first + 1;
			add_range(max(first, last - ost + 1), last, 1);

		}

		if(tip == 'C') {
			int A, B;
			cin >> A >> B;

			int L = 0;
			{
				int l = 1, r = n, ans = n + 1;
				while(l <= r) {
					int mid = (l + r) / 2;
					if(query(mid) >= A) {
						ans = mid;
						r = mid - 1;
					} else l = mid + 1;
				}

				L = ans;
			}

			int R = 0;
			{
				int l = 1, r = n, ans = 0;
				while(l <= r) {
					int mid = (l + r) / 2;
					if(query(mid) <= B) {
						ans = mid;
						l = mid + 1;
					} else r = mid - 1;
				}

				R = ans;

			}

			cout << R - L + 1 << '\n';

		}

	}

	return 0;
}
/**

5 7
1 3 2 5 2
F 2 1
F 2 3
C 6 8
F 2 1
F 2 2
C 3 5

// probati bojenje sahovski ili slicno

**/

• 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