Submission #1256875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256875		kerem	Growing Trees (BOI11_grow)	C++20	0 / 100	72 ms	7748 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[8*N];

void init(int x=1,int l=1,int r=n){
	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]=st[2*x+1];
}
void push(int x){
	if(lz[x]){
		st[x]+=lz[x];
		lz[2*x]+=lz[x];
		lz[2*x+1]+=lz[x];
		lz[x]=0;
	} 
}
int upperbound(int k,int x=1,int l=1,int r=n){
	if(k>=st[x]) return r+1;
	if(l==r) return l;
	push(2*x);
	int mid=(l+r)/2;
	if(st[2*x]<=k) return upperbound(k,2*x+1,mid+1,r);
	else return upperbound(k,2*x,l,mid);
}
void update(int ql,int qr,int x=1,int l=1,int r=n){
	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(ql,qr,2*x,l,mid);
	update(ql,qr,2*x+1,mid+1,r);
	st[x]=st[2*x+1];
}
int query(int k,int x=1,int l=1,int r=n){
	if(r<k || k<l) return 0;
	push(x);
	if(l==r)
		return st[x];
	int mid=(l+r)/2;
	return query(k,2*x,l,mid)+query(k,2*x+1,mid+1,r);
}
void solve(){
	cin >> n >> q;
	for(int i=1;i<=n;i++)
		cin >> a[i];
	sort(a+1,a+n+1);
	init();
	while(q--){
		char c;
		cin >> c;
		if(c=='F'){
			int t,x;
			cin >> t >> x;
			int l=upperbound(x-1);
			if(l<=n){
				if(l+t-1>n)
					update(l,n);
				else{
					int k=query(l+t-1);
					int r=upperbound(k-1)-1;
					update(l,r);
					t-=r-l+1;
					r=upperbound(k)-1;
					l=r-t+1;
					update(l,r);
				}
			}
		}
		if(c=='C'){
			int x,y;
			cin >> x >> y;
			cout << upperbound(y)-upperbound(x-1) << "\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