Submission #676500

#	Time	Username	Problem	Language	Result	Execution time	Memory
676500		penguin133	Growing Trees (BOI11_grow)	C++17	100 / 100	110 ms	4060 KiB

grow

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pair<int, int> > 
#define fi first
#define se second
int n, q;
int ft[100005], A[100005];
void upd(int l, int r, int v){
	r++;
	for(;l<=n;l+=(l & -l))ft[l] += v;
	for(;r<=n;r+=(r & -r))ft[r] -= v;
}
int query(int p){
	int sum = 0;
	for(;p;p-=(p & -p))sum += ft[p];
	return sum;
}
void solve(){
	cin >> n >> q;
	for(int i=1;i<=n;i++){
		int x;cin >> x;
		A[i] = x;
	}
	sort(A+1, A+n+1);
	for(int i=1;i<=n;i++)upd(i, i, A[i]);
	while(q--){
		char x;cin >> x;
		if(x == 'F'){
			int a,b;cin >> a >> b;
			int s = 1, e = n, ans = e+1;
			while(s <= e){
				int m = (s + e)/2;
				if(query(m) >= b)ans = m, e = m - 1;
				else s = m + 1;
			}
			if(n-ans+1 <= a)upd(ans, n, 1);
			else{
				int tmp = query(ans + a - 1);
				s = 1, e = n; int ans2 = e+1;
				while(s <= e){
					int m = (s + e)/2;
					if(query(m) >= tmp)ans2 = m, e=  m - 1;
					else s = m + 1;
				}
				s = 1, e = n; int ans3 = 0;
				while(s <= e){
					int m = (s + e)/2;
					if(query(m) <= tmp)ans3 = m, s = m + 1;
					else e = m - 1;
				}
				upd(ans, ans2 - 1, 1);
				upd(ans3 - (ans+a-1 - ans2), ans3, 1);
			}
		}
		else{
			int a,b;cin >> a >> b;
			int s = 1, e = n, ans = 0, ans2 = 0;
			while(s <= e){
				int m = (s + e)/2;
				if(query(m) < a)s = m + 1, ans = m;
				else e = m - 1;
			}
			s = 1, e = n;
			while(s <= e){
				int m = (s + e)/2;
				if(query(m) <= b)s = m + 1, ans2 = m;
				else e = m - 1;
			}
			cout << ans2-ans << '\n';
		}
	}
	
}
 
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Compilation message (stderr)

grow.cpp:77:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   77 | main(){
      | ^~~~

• 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