제출 #1288928

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288928		EkinOnal	Growing Trees (BOI11_grow)	C++20	100 / 100	961 ms	8772 KiB

grow

//#pragma GCC optimize("O3,unroll-loops,Ofast")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#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;
 
#define MAX 200005
#define pb push_back
// #define mp make_pair 
#define int long long
#define f first
#define s second
#define vi vector<int>
#define pii pair<int,int>
#define si set<int>
#define vpii vector<pair<int,int>> 
const int mod = 1e9+7;
const int INF = 1e18;
// myMap.begin()->first :  key
// myMap.begin()->second : value
 
int epow(int a,int b){int ans=1;while(b){if(b&1) ans*=a;a*=a;b>>=1;ans%=mod;a%=mod;}return ans%mod;}
int gcd(int a,int b) {if(a<b)swap(a,b);while(b){int tmp=b;b=a%b;a=tmp;}return a;}
int mul(int a,int b){return ((a%mod)*(b%mod))%mod;}
int sum(int a,int b){return ((a%mod)+(b%mod))%mod;}
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
//typedef
// tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_multiset;

int n,m; 
vi arr(MAX),segt(MAX*2),lazy(MAX*2); 
void build(int v,int tl,int tr){
	if(tl==tr){
		segt[v]=arr[tl];
		return;
	}
	int mid=(tl+tr)>>1;
	build(v*2,tl,mid); build(v*2+1,mid+1,tr);
	segt[v]=min(segt[v*2],segt[v*2+1]);
}

void push(int v,int tl,int tr){
	if(!lazy[v]) return;
	if(tl!=tr){
		lazy[v*2]+=lazy[v];
		lazy[v*2+1]+=lazy[v];
	}
	segt[v]+=lazy[v];
	lazy[v]=0;
}

void update(int v,int tl,int tr,int l,int r){
	if(tl>r || tr<l) return;
	push(v,tl,tr);
	if(tl>=l && tr<=r){
		lazy[v]=1;
		push(v,tl,tr);
		return;
	}
	int mid=(tl+tr)>>1;
	update(v*2,tl,mid,l,r); update(v*2+1,mid+1,tr,l,r);
	segt[v]=min(segt[v*2],segt[v*2+1]);
}

int query(int v,int tl,int tr,int l,int r){
	push(v,tl,tr);
	if(tl>r || tr<l) return INF;
	if(tl>=l && tr<=r) return segt[v];
	int mid=(tl+tr)>>1;
	int a=query(v*2,tl,mid,l,r), b=query(v*2+1,mid+1,tr,l,r);
	return min(a,b);
}


void solve(){ 
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>arr[i];

	sort(arr.begin()+1,arr.begin()+n+1);
//	for(auto u : v) cout<<u<<" ";cout<<endl;

	build(1,1,n);
	// cout<<query(1,1,n,1,5)<<endl;
	// update(1,1,n,1,1);
	// cout<<query(1,1,n,1,5)<<endl;


	while(m--){
		char c; cin>>c;
		if(c=='F'){
			int adet,h; cin>>adet>>h;

			int l=1,r=n;
			while(l<=r){
				int mid=(l+r)>>1;
				if(query(1,1,n,mid,mid)<h) l=mid+1;
				else r=mid-1;
			}

			int ilk=l,son=min(n,l+adet-1),type=query(1,1,n,son,son);
			adet=son-ilk+1; //cout<<adet<<" 23\n";

			l=ilk,r=son;
			while(l<=r){
				int mid=(l+r)>>1;
				if(query(1,1,n,mid,mid)==type) r=mid-1;
				else l=mid+1;
			}	

			if(query(1,1,n,ilk,ilk)!=query(1,1,n,son,son)){
				update(1,1,n,ilk,r); //cout<<"upd : "<<ilk<<" "<<l<<endl;
				adet -= (r-ilk+1);
			}

			l=son,r=n;
			while(l<=r){
				int mid=(l+r)>>1;
				if(query(1,1,n,mid,mid)!=type) r=mid-1;
				else l=mid+1;
			}	
			update(1,1,n, r-adet+1 ,r); //cout<<"upd : "<<l-adet+1<<" "<<l<<endl;


		}	
		else{
			int mn,mx; cin>>mn>>mx;

			int l=1,r=n;
			while(l<=r){
				int mid=(l+r)>>1;
				if(query(1,1,n,mid,mid)<mn) l=mid+1;
				else r=mid-1;
			}
			int start=l;

			l=1,r=n;
			while(l<=r){
				int mid=(l+r)>>1;
				if(query(1,1,n,mid,mid)>mx) r=mid-1;
				else l=mid+1;
			}
			cout<<r-start+1<<endl;
			// cout<<start<<" "<<l<<endl;

		}	
	}	



}	
	
int32_t main(/*int32_t argc, char* argv[]*/){
	std::ios_base::sync_with_stdio(0); std::cin.tie(0);	

	int t=1;
	// cin >> t;
	while (t--) solve();
 	
	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