Submission #1256746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256746		kerem	Growing Trees (BOI11_grow)	C++20	0 / 100	74 ms	6724 KiB

grow

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define inf 1e15
#define N 100000
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tuple<int,int,int> tiii;
typedef pair<int,int> pii;


int n,q,a[N+5],st[4*N],lz[4*N];

void init(int x,int l,int r){
	if(l==r){
		st[x]=a[l];
		return;
	}
	int mid=(l+r)/2;
	init(2*x,l,mid);
	init(2*x+1,mid+1,r);
	st[x]=max(st[2*x],st[2*x+1]);
}
void push(int x){
	if(lz[x]){
		st[x]+=lz[x];
		if(2*x<4*N){
			lz[2*x]+=lz[x];
			lz[2*x+1]+=lz[x];
		}
		lz[x]=0;
	} 
}
int bs(int x,int l,int r,int k){
	if(l==r) return l;
	push(2*x);
	int mid=(l+r)/2;
	if(st[2*x]<=k) return bs(2*x+1,mid+1,r,k);
	else return bs(2*x,l,mid,k);
}
void update(int x,int l,int r,int ql,int qr){
	push(x);
	if(r<ql || qr<l) return;
	if(ql<=l && r<=qr){
		lz[x]+=1;
		push(x);
		return;
	}
	int mid=(l+r)/2;
	update(2*x,l,mid,ql,qr);
	update(2*x+1,mid+1,r,ql,qr);
	st[x]=max(st[2*x],st[2*x+1]);
}
int query(int x,int l,int r,int k){
	if(r<k || k<l) return 0;
	push(x);
	if(l==r)
		return st[x];
	int mid=(l+r)/2;
	return query(2*x,l,mid,k)+query(2*x+1,mid+1,r,k);
}
void solve(){
	cin >> n >> q;
	for(int i=1;i<=n;i++)
		cin >> a[i];
	sort(a+1,a+n+1);
	init(1,1,n);
	while(q--){
		char c;
		cin >> c;
		if(c=='F'){
			int t,x;
			cin >> t >> x;
			int l=bs(1,1,n,x-1);
			if(l+t-1>n)
				update(1,1,n,l,n);
			else{
				int k=query(1,1,n,l+t-1);
				int r=bs(1,1,n,k-1)-1;
				update(1,1,n,l,r);
				t-=r-l+1;
				r=bs(1,1,n,k)-1;
				l=r-t+1;
				update(1,1,n,l,r);
			}
		}
		if(c=='C'){
			int x,y;
			cin >> x >> y;
			int r=(y>=st[1]?n+1:bs(1,1,n,y));
			int l=(x>st[1]?n+1:bs(1,1,n,x-1));
			cout << r-l << "\n";
		}
	}
}
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	int test=1;
	//~ cin >> test;
	while(test--) solve();
}

• 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