Submission #941534

#	Time	Username	Problem	Language	Result	Execution time	Memory
941534		tamir1	Growing Trees (BOI11_grow)	C++17	0 / 100	402 ms	4128 KiB

grow

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,i,x,y,a[100005],s[400005];
char type;
void build(ll node,ll l,ll r){
	if(l==r){
		s[node]=a[l];
		return;
	}
	ll mid=(r+l)/2;
	build(node*2,l,mid);
	build(node*2+1,mid+1,r);
}
ll get(ll node,ll l,ll r,ll loc){
	if(l>loc || r<loc) return 0;
	if(r==l) return s[node];
	ll mid=(r+l)/2;
	return s[node]+get(node*2,l,mid,loc)+get(node*2+1,mid+1,r,loc);
}
ll find(ll x,ll y){
	if(get(1,1,n,1)>y || get(1,1,n,n)<x) return 0;
	ll l1=1,r1=n,l2=1,r2=n;
	while(r1-l1>1){
		ll mid=(l1+r1+1)/2;
		if(get(1,1,n,mid)<x) l1=mid;
		else r1=mid;
	}
	if(get(1,1,n,l1)<x) l1=r1;
	while(r2-l2>1){
		ll mid=(r2+l2+1)/2;
		if(get(1,1,n,mid)>y) r2=mid;
		else l2=mid;
	}
	if(get(1,1,n,r2)>y) r2=l2;
	return r2-l1+1;
}
void update(ll node,ll l,ll r,ll L,ll R){
	if(l>R || r<L) return;
	if(l>=L && r<=R){
		s[node]++;
		return;
	}
	ll mid=(r+l)/2;
	update(node*2,l,mid,L,R);
	update(node*2+1,mid+1,r,L,R);
}
void change(ll c,ll h){
	ll l=1,r=n;
	if(get(1,1,n,n)<h) return;
	while(r-l>1){
		ll mid=(r+l+1)/2;
		if(get(1,1,n,mid)<h) l=mid;
		else r=mid;
	}
	if(get(1,1,n,l)<h) l=r;
	if(l+c-1>=n){
		update(1,1,n,l,n);
		return;
	}
	r=l+c-1;
	ll val=get(1,1,n,r);
	ll l1=1,r1=n;
	while(r1-l1>1){
		ll mid=(r1+l1+1)/2;
		if(get(1,1,n,mid)>=val) r1=mid;
		else l1=mid;
	}
	if(r1>=val) r1=l1;
	update(1,1,n,l,r1);
	c=c-(r1-l+1);
	l=1;
	r=n;
	while(r-l>1){
		ll mid=(r+l+1)/2;
		if(get(1,1,n,mid)<=val) l=mid;
		else r=mid;
	}
	if(get(1,1,n,r)>val) r=l;
	update(1,1,n,r-c+1,r);
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(i=1;i<=n;i++) cin >> a[i];
	sort(a+1,a+n+1);
	build(1,1,n);
	while(m--){
		cin >> type >> x >> y;
		if(type=='C'){
			cout << find(x,y) << "\n";
		}
		else{
			change(x,y);
		}
	}
}

• 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