oj.uz

Submission #384940

# Submission time Handle Problem Language Result Execution time Memory
384940 2021-04-02T17:29:36 Z ritul_kr_singh Growing Trees (BOI11_grow) C++17
100 / 100
 130 ms 4332 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 3052 KB Output is correct
2 Correct 123 ms 3436 KB Output is correct
3 Correct 93 ms 3308 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 364 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
3 Correct 4 ms 492 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 53 ms 1516 KB Output is correct
6 Correct 66 ms 1788 KB Output is correct
7 Correct 5 ms 492 KB Output is correct
8 Correct 28 ms 1260 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 1772 KB Output is correct
2 Correct 67 ms 1960 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 40 ms 1388 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 2028 KB Output is correct
2 Correct 74 ms 1900 KB Output is correct
3 Correct 8 ms 640 KB Output is correct
4 Correct 80 ms 1900 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 2540 KB Output is correct
2 Correct 110 ms 2924 KB Output is correct
3 Correct 20 ms 1004 KB Output is correct
4 Correct 75 ms 3052 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 2668 KB Output is correct
2 Correct 109 ms 3008 KB Output is correct
3 Correct 100 ms 3052 KB Output is correct
4 Correct 22 ms 1004 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 2796 KB Output is correct
2 Correct 78 ms 3052 KB Output is correct
3 Correct 94 ms 3316 KB Output is correct
4 Correct 19 ms 1024 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 3436 KB Output is correct
2 Correct 108 ms 2924 KB Output is correct
3 Correct 32 ms 2668 KB Output is correct
4 Correct 68 ms 2924 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 3180 KB Output is correct
2 Correct 117 ms 3436 KB Output is correct
3 Correct 130 ms 3820 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 4332 KB Output is correct