oj.uz

Submission #669123

# Submission time Handle Problem Language Result Execution time Memory
669123 2022-12-05T19:28:37 Z Koful123 Growing Trees (BOI11_grow) C++17
100 / 100
 72 ms 4276 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2952 KB Output is correct
2 Correct 63 ms 3472 KB Output is correct
3 Correct 38 ms 3252 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 328 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 29 ms 1356 KB Output is correct
6 Correct 36 ms 1596 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 21 ms 1264 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1708 KB Output is correct
2 Correct 39 ms 1820 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 25 ms 1352 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1864 KB Output is correct
2 Correct 39 ms 1688 KB Output is correct
3 Correct 4 ms 456 KB Output is correct
4 Correct 36 ms 1776 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 2480 KB Output is correct
2 Correct 57 ms 2816 KB Output is correct
3 Correct 11 ms 980 KB Output is correct
4 Correct 33 ms 2820 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 2552 KB Output is correct
2 Correct 67 ms 2956 KB Output is correct
3 Correct 36 ms 3028 KB Output is correct
4 Correct 12 ms 968 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 2688 KB Output is correct
2 Correct 40 ms 2960 KB Output is correct
3 Correct 39 ms 3232 KB Output is correct
4 Correct 11 ms 980 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 3392 KB Output is correct
2 Correct 59 ms 2776 KB Output is correct
3 Correct 22 ms 2600 KB Output is correct
4 Correct 38 ms 2800 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 3192 KB Output is correct
2 Correct 63 ms 3372 KB Output is correct
3 Correct 62 ms 3660 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 4276 KB Output is correct