Submission #490483

#	Time	Username	Problem	Language	Result	Execution time	Memory
490483		BackNoob	Growing Trees (BOI11_grow)	C++14	100 / 100	141 ms	4536 KiB

grow

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1) 
#define TASK "task"
#define sz(s) (int) (s).size()

using namespace std;
const int mxN = 3e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

int n , q;
int a[mxN];
int t[mxN * 4];
int lazy[mxN * 4];

void build(int v , int tl , int tr)
{
	if(tl == tr) t[v] = a[tl];
	else {
		int tm = (tl + tr) / 2;
		build(v * 2 , tl , tm);
		build(v * 2 + 1 , tm + 1 , tr);
		t[v] = max(t[v * 2] , t[v * 2 + 1]);
	}
}

void modify(int v)
{
	t[v * 2] += lazy[v];
	t[v * 2 + 1] += lazy[v];
	lazy[v * 2] += lazy[v];
	lazy[v * 2 + 1] += lazy[v];
	lazy[v] = 0;
}

void update(int v , int tl , int tr , int l , int r)
{
	if(l > r) return ;
	if(tl == l && tr == r) {
		t[v]++;
		lazy[v]++;
		return;
	}
	int tm = (tl + tr) / 2;
	modify(v);
	update(v * 2 , tl , tm , l , min(r , tm));
	update(v * 2 + 1 , tm + 1 , tr , max(l , tm + 1) , r);
	t[v] = max(t[v * 2] , t[v * 2 + 1]);
}

int findfst(int v , int tl , int tr , int x)
{
	if(t[v] < x) return n + 1;
	if(tl == tr) return tl;
	modify(v);
	int tm = (tl + tr) / 2;
	if(t[v * 2] >= x) return findfst(v * 2 , tl , tm , x);
	return findfst(v * 2 + 1 , tm + 1 , tr , x);
}

int getidx(int v , int tl , int tr , int pos)
{
	if(tl == tr && tl == pos) return t[v];
	modify(v);
	int tm = (tl + tr) / 2;
	if(pos <= tm) return getidx(v * 2 , tl , tm , pos);
	return getidx(v * 2 + 1 , tm + 1 , tr , pos);
}

int getidx(int pos)
{
	return getidx(1 , 1 , n , pos);
}

int findfst(int x)
{
	return findfst(1 , 1 , n , x);
}

void update(int l , int r)
{
	update(1 , 1 , n , l , r);
}

void solve()
{
	cin >> n >> q;
	for(int i = 1 ; i <= n ; i++) cin >> a[i];

	sort(a + 1 , a + 1 + n);	
	build(1 , 1 , n);

	while(q--) {
		char cmd;
		cin >> cmd;
		if(cmd == 'F') {
			int c , h;
			cin >> c >> h;
			int l1 = findfst(h);
			int r1 = min(n , l1 + c - 1);

			if(r1 == n) {
				update(l1 , r1);
				continue;
			}

			int val = getidx(r1);

			int r2 = findfst(val);

			update(l1 , r2 - 1);

			int r3 = findfst(val + 1);

			int re = c - max(0 , (r2 - 1 - l1 + 1));
			update(max(r2 , r3 - 1 - re + 1) , r3 - 1);
		}
		else {
			int l , r;
			cin >> l >> r;
			cout << findfst(r + 1) - 1 - findfst(l) + 1 << endl;
		}
	}

}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    // freopen(TASK".in" , "r" , stdin);
    // freopen(TASK".out" , "w" , stdout);
    
    int tc = 1;
    //cin >> tc;
    while(tc--) {
    	solve();
    }
    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