Submission #384940

#	Time	Username	Problem	Language	Result	Execution time	Memory
384940		ritul_kr_singh	Growing Trees (BOI11_grow)	C++17	100 / 100	130 ms	4332 KiB

grow

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

struct FenwickTree{
	vector<int> a; int n, s;
	FenwickTree(int N){ a.resize((n=N)+1); }
	void add(int i, int v){
		for(++i; i<=n; i+=i&-i) a[i] += v;
	}
	int get(int i){
		s = 0;
		for(++i; i>=1; i-=i&-i) s += a[i];
		return s;
	}
};

int bs0(int i, FenwickTree &x){ //lower_bound
	int low = 0, high = x.n - 1;
	while(low<high){
		int mid = (low+high)/2;
		if(x.get(mid)>=i) high = mid;
		else low = mid+1;
	}
	return low;
}

int bs1(int i, FenwickTree &x){ // last <=i
	int low = 0, high = x.n - 1;
	while(low<high){
		int mid = (low+high)/2;
		if(x.get(mid+1)<=i) low = mid+1;
		else high = mid;
	}
	return low;
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, m, x, y, low, high; cin >> n >> m;
	int inp[n+1];
	for(int i=1; i<=n; ++i) cin >> inp[i];
	sort(inp+1, inp+n+1);
	inp[0] = 0;

	FenwickTree a(n);
	for(int i=0; i<n; ++i) a.add(i, inp[i+1] - inp[i]);

	while(m--){
		char t; cin >> t >> x >> y;
		if(t=='F'){
			if(a.get(n-1) < y) continue;
			int l = bs0(y, a);
			int r = min(n-1, l+x-1);
			if(l+x-1 >= n) x=n-l;
			int g = a.get(r);
			int firstG = bs0(g, a);
			int lastG = bs1(g, a);
			int left = x - (firstG-l);
			a.add(l, 1);
			a.add(firstG, -1);
			a.add(lastG-left+1, 1);
			a.add(lastG+1, -1);
		}else{
			if(a.get(0)>y or a.get(n-1)<x) cout << 0 nl;
			else{
				int l = bs0(x, a);
				int r = bs1(y, a);
				cout << r-l+1 nl;
			}
		}
	}
}

Compilation message (stderr)

grow.cpp: In function 'int main()':
grow.cpp:42:18: warning: unused variable 'low' [-Wunused-variable]
   42 |  int n, m, x, y, low, high; cin >> n >> m;
      |                  ^~~
grow.cpp:42:23: warning: unused variable 'high' [-Wunused-variable]
   42 |  int n, m, x, y, low, high; cin >> n >> m;
      |                       ^~~~

• 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