oj.uz

Submission #676500

# Submission time Handle Problem Language Result Execution time Memory
676500 2022-12-31T03:49:36 Z penguin133 Growing Trees (BOI11_grow) C++17
100 / 100
 110 ms 4060 KB 
#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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 3020 KB Output is correct
2 Correct 110 ms 3508 KB Output is correct
3 Correct 36 ms 3240 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 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 45 ms 1452 KB Output is correct
6 Correct 50 ms 1660 KB Output is correct
7 Correct 4 ms 432 KB Output is correct
8 Correct 27 ms 1108 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 1620 KB Output is correct
2 Correct 52 ms 1792 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 31 ms 1356 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1864 KB Output is correct
2 Correct 56 ms 1676 KB Output is correct
3 Correct 5 ms 468 KB Output is correct
4 Correct 50 ms 1824 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 2472 KB Output is correct
2 Correct 88 ms 2740 KB Output is correct
3 Correct 15 ms 980 KB Output is correct
4 Correct 31 ms 2784 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 2556 KB Output is correct
2 Correct 89 ms 2944 KB Output is correct
3 Correct 35 ms 3164 KB Output is correct
4 Correct 16 ms 996 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 2724 KB Output is correct
2 Correct 66 ms 3004 KB Output is correct
3 Correct 36 ms 3268 KB Output is correct
4 Correct 15 ms 980 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 3336 KB Output is correct
2 Correct 89 ms 2760 KB Output is correct
3 Correct 26 ms 2572 KB Output is correct
4 Correct 60 ms 2792 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 3132 KB Output is correct
2 Correct 99 ms 3288 KB Output is correct
3 Correct 95 ms 3640 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 4060 KB Output is correct