Submission #669123

#	Time	Username	Problem	Language	Result	Execution time	Memory
669123		Koful123	Growing Trees (BOI11_grow)	C++17	100 / 100	72 ms	4276 KiB

grow

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

//...wait

const int lg = 20;
struct Fenwick{
	int n; vector<int> fw;
	Fenwick(int _n){
		fw.assign((n = _n) + 1,0);
	};
	void upd(int pos,int x){
		for( ; pos <= n; pos += (pos & -pos)){
			fw[pos] += x;
		}
	}
	int get(int pos){
		int res = 0; for(; pos; pos -= (pos & -pos)){
			res += fw[pos];
		}
		return res;
	}
	int find(int x){
		int pos = 0;
		for(int i = lg; i >= 0; i--){
			if(pos + (1 << i) <= n && fw[pos + (1 << i)] < x){
				pos += (1 << i);
				x -= fw[pos]; 
			}
		}
		return pos + 1;
	}
	void upd(int l,int r,int x){
		upd(l,x), upd(r+1,-x);
	}
};	
	
void solve(){

	int n,q;
	cin >> n >> q;

	vector<int> v(n + 1);
	for(int i = 1; i <= n; i++){
		cin >> v[i];
	}

	Fenwick fw(n); sort(1 + all(v));
	for(int i = 1; i <= n; i++){
		fw.upd(i,i,v[i]);
	}

	for(int i = 0; i < q; i++){
		char c; cin >> c;
		if(c == 'F'){
			int c,h; cin >> c >> h;
			int pos = fw.find(h);
			if(pos + c - 1 > n){
				fw.upd(pos,n,1);
				continue;
			}
			int last = fw.get(pos + c - 1);
			int high = fw.find(last + 1);
			int low = fw.find(last);	

			fw.upd(pos,low-1,1), fw.upd(high - (pos + c - low),high - 1,1);
		}
		else{
			int l,r; cin >> l >> r;
			cout << fw.find(r + 1) - fw.find(l) << endl;
		}
	}

}	
 
signed main(){

	ios::sync_with_stdio(0);
	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