Submission #1150346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150346		rayan_bd	Growing Trees (BOI11_grow)	C++20	100 / 100	329 ms	7840 KiB

grow

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 


#define getar(ar,n) for(ll i=0;i<n;++i) cin>>ar[i]
#define show(n) cout<<n<<'\n'
#define all(v) v.begin(), v.end()
#define br cout<<"\n"
#define pb push_back
#define nl '\n'
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define ret return
#define ll long long
#define ld long double
#define sza(x) ((int)x.size())
#define fi first
#define se second

const int mxN = 1e6 + 500;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;


ll ar[mxN],seg[mxN*4],lazy[mxN*4];

struct seg_tree{
	void build(ll node,ll start,ll end){
		if(start==end){
			seg[node]=ar[start];
			return;
		}
		ll mid=start+(end-start)/2;
		build(node*2+1,start,mid);
		build(node*2+2,mid+1,end);
		seg[node]=min(seg[node*2+1],seg[node*2+2]);
	}
	void push(ll node,ll start,ll end){
		if(lazy[node]==0) return;
		seg[node]+=lazy[node];
		lazy[node*2+1]+=lazy[node];
		lazy[node*2+2]+=lazy[node];
		lazy[node]=0;
	}
	void update(ll node,ll start,ll end,ll l,ll r,ll v){
		push(node,start,end);
		if(start>r||end<l) return;
		if(start>=l&&end<=r){
			lazy[node]=1;
			push(node,start,end);
			return;
		}
		ll mid=start+(end-start)/2;
		update(node*2+1,start,mid,l,r,v);
		update(node*2+2,mid+1,end,l,r,v);
		seg[node]=min(seg[node*2+1],seg[node*2+2]);
	}
	ll qry(ll node,ll start,ll end,ll idx){
		push(node,start,end);
		if(start==end) return seg[node];
		ll mid=start+(end-start)/2;
		if(idx<=mid) return qry(node*2+1,start,mid,idx);
		return qry(node*2+2,mid+1,end,idx);
	}
} tr;

pair<ll,ll> find_range(ll v,ll n){
	pair<ll,ll> res;
	ll st=1,en=n;
	while(st<=en){
		ll mid=st+(en-st)/2;
		ll point=tr.qry(0,1,n,mid);
		if(point>=v){
			res.fi=mid;
			en=mid-1;
		}else{
			st=mid+1;
		}
	}
	st=1,en=n;
	while(st<=en){
		ll mid=st+(en-st)/2;
		ll point=tr.qry(0,1,n,mid);
		if(point<=v){
			res.se=mid;
			st=mid+1;
		}else{
			en=mid-1;
		}
	}
	return res;
}

void lets_go() {
   ll n,q,l,r;cin>>n>>q;
   char ch;
   for(ll i=1;i<=n;++i) cin>>ar[i];
   sort(ar+1,ar+n+1);
   tr.build(0,1,n);
   while(q--){
   	cin>>ch>>l>>r;
   	if(ch=='C'){
   		ll mini=-1,maxi=-1,st=1,en=n;
   		while(st<=en){
   			ll mid=st+(en-st)/2;
   			ll point=tr.qry(0,1,n,mid);
   			if(point>=l){
   				mini=mid;
   				en=mid-1;
   			}else{
   				st=mid+1;
   			}
   		}
   		st=1,en=n;
   		while(st<=en){
   			ll mid=st+(en-st)/2;
   			ll point=tr.qry(0,1,n,mid);
   			if(point<=r){
   				maxi=mid;
   				st=mid+1;
   			}else{
   				en=mid-1;
   			}
   		}
   		if(mini==-1||maxi==-1){
   			show(0);
   			continue;
   		}
   		show(maxi-mini+1);
   	}else{
   		ll st=1,en=n,mini=-1;
   		while(st<=en){
   			ll mid=st+(en-st)/2;
   			ll point=tr.qry(0,1,n,mid);
   			if(point>=r){
   				mini=mid;
   				en=mid-1;
   			}else{
   				st=mid+1;
   			}
   		}
   		if(mini==-1) continue;
   		ll maxi=min(n,mini+l-1);


   		if(maxi==n){
   			tr.update(0,1,n,mini,maxi,1);
   		}else{
   			ll mxx=tr.qry(0,1,n,maxi);
   			pair<ll,ll> maxi_range=find_range(mxx,n);
   			ll maxi_without_max=maxi_range.fi-1;
   			if(maxi_without_max>=mini){
   				tr.update(0,1,n,mini,maxi_without_max,1);
   			}
   			ll leftt=(maxi-mini+1)-(maxi_without_max-mini+1);
   			tr.update(0,1,n,maxi_range.se-leftt+1,maxi_range.se,1);
   		}
   	}
   }
/*  for(ll i=1;i<=n;++i){
   	cout<<tr.qry(0,1,n,i)<<" ";
   }br;*/
}

signed main() {
    

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    lets_go();

    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