Submission #964549

#	Time	Username	Problem	Language	Result	Execution time	Memory
964549		pcc	Growing Trees (BOI11_grow)	C++17	0 / 100	1073 ms	1768 KiB

grow

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 1e5+10;

struct BIT{
	int bit[mxn];
	void modify(int p,int v){
		if(!p)p = 1;
		for(;p<mxn;p+=p&-p)bit[p] += v;
		return;
	}
	int getval(int p){
		int re = 0;
		for(;p>0;p-= p&-p)re += bit[p];
		return re;
	}
};

int arr[mxn];
int N,Q;
BIT bit;

int getleft(int tar){
	int l = 0,r = N+1;
	while(l != r){
		int mid = (l+r)>>1;
		if(bit.getval(mid)>=tar)r = mid;
		else l = mid+1;
	}
	return l;
}

void add(int a,int b){
	a= getleft(a);
	b = min(N,a+b-1);
	if(a>N)return;
	int lp = getleft(bit.getval(b));
	int rp = getleft(bit.getval(b)+1)-1;
	assert(a<=lp&&lp<=rp&&lp<=b);
	bit.modify(a,1);
	bit.modify(lp,-1);
	int len = b-lp+1;
	bit.modify(rp-len+1,1);
	bit.modify(rp+1,-1);
	for(int i = 1;i<=N+1;i++){
		assert(bit.getval(i)>=bit.getval(i-1));
	}
	return;
}

int btw(int a,int b){
	int ta = getleft(a);
	int tb = getleft(b+1);
	assert(tb>=ta);
	return tb-ta;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	for(int i = 1;i<=N;i++)cin>>arr[i];
	sort(arr+1,arr+N+1);
	for(int i = 1;i<=N;i++)bit.modify(i,arr[i]-arr[i-1]);
	bit.modify(N+1,(int)1e9);
	while(Q--){
		char t;
		int a,b;
		cin>>t>>a>>b;
		if(t == 'F')add(b,a);
		else cout<<btw(a,b)<<'\n';
	}
	return 0;
}

• 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