Submission #954556

#	Time	Username	Problem	Language	Result	Execution time	Memory
954556		Amaarsaa	Growing Trees (BOI11_grow)	C++14	0 / 100	343 ms	11308 KiB

grow

#include<bits/stdc++.h>

using namespace std;
#define lc (p<<1)
#define rc (p<<1) + 1
using ll = long long ;
const ll N = 1e5 + 4;
pair < ll, ll > P[N];
ll a[N], n;

struct node {
	ll lzadd;
	ll min;
};
node tree[8 * N + 2];

void pushdown(ll p, ll lo, ll hi) {
	if ( tree[p].lzadd != 0) {
		tree[lc].lzadd += tree[p].lzadd;
		tree[lc].min += tree[p].lzadd;
		tree[rc].lzadd += tree[p].lzadd;
		tree[rc].min += tree[p].lzadd;
		tree[p].lzadd = 0;
	}
	return ;
}

void pushup(ll p, ll lo, ll hi) {
	tree[p].min = min(tree[lc].min, tree[rc].min);
}

void Build (ll p, ll lo, ll hi) {
	ll mid = (lo + hi)/2;
	tree[p].lzadd = 0;
	if ( lo == hi) {
		tree[p].min = a[lo];
		return ;
	}
	Build(lc, lo, mid);
	Build(rc, mid + 1, hi);
	pushup(p, lo, hi);
	return ;
}
ll find(ll p, ll lo, ll hi, ll x) {
	ll mid = (lo + hi)/2;
	pushdown(p, lo, hi);
	if ( lo == hi) return tree[p].min;
	if ( x <= mid) return find(lc, lo, mid, x);
	return find(rc, mid + 1, hi, x);
}
void update(ll p, ll lo, ll hi, ll l, ll r, ll x) {
	ll mid = (lo + hi)/2;
	pushdown(p, lo, hi);
	if ( lo > r || l > hi) return ;
	if ( l <= lo && hi <= r) {
		tree[p].lzadd = x;
		tree[p].min += x;
		return ;
	}
	update(lc, lo, mid, l, r, x);
	update(rc, mid + 1, hi, l, r, x);
	pushup(p, lo, hi);
}
ll lowerb(ll x) {
	if ( x > find(1, 1, n, n)) return n +1;
	ll lo, hi, mid;
	lo = 1;
	hi = n;
	while ( lo < hi) {
		mid = (lo + hi)/2;
		if (find(1, 1, n, mid) < x) lo = mid + 1;
		else hi =mid;
	}
	return lo;
}
ll upperb(ll x) {
	if ( x > find(1, 1, n, n)) return n +1;
	ll lo, hi, mid;
	lo = 1;
	hi = n;
	while ( lo < hi) {
		mid = (lo + hi)/2;
		if (find(1, 1, n, mid) <= x) lo = mid + 1;
		else hi =mid;
	}
	return lo;
}
int main() {
//	freopen("moocast.in", "r", stdin);
//	freopen("moocast.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	ll q, i, x, l, y, j, s;
	
	cin >> n >> q;
	
	for (i = 1; i <= n; i ++) cin >> a[i];
	
	sort ( a + 1, a + n + 1);
	
	
	Build(1, 1, n);
	
	char ch;
	while ( q-- ) {
		cin >> ch;
		if ( ch == 'F') {
			cin >> x >> y;
			swap(x, y);
			l = lowerb(x);
			if ( l + y - 1 >= n) {
				update(1, 1, n, l, n, 1);
			}
			else {
				s = lowerb(find(1, 1, n, l + y - 1));
				update(1, 1, n, l,s - 1, 1);
		//		cout << x << " " << l << " " << s << endl;
				y -= (s - l);
		//		cout << y << ">" << endl;
				s = upperb(find(1, 1, n, l + y - 1));
				s --;
			//	cout << s << endl;
				update(1, 1, n, s - y + 1, s, 1);
			}
		}
		else {
			cin >> x >> y;
			cout << lowerb(y + 1) - lowerb(x) << endl;
		}
	//	for (j= 1; j <= n; j ++) cout << find(1, 1, n, j) << " ";
	//	cout << endl;
	}
}

Compilation message (stderr)

grow.cpp: In function 'int main()':
grow.cpp:93:20: warning: unused variable 'j' [-Wunused-variable]
   93 |  ll q, i, x, l, y, j, s;
      |                    ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10