oj.uz

Submission #717369

# Submission time Handle Problem Language Result Execution time Memory
717369 2023-04-01T21:49:52 Z bane Growing Trees (BOI11_grow) C++17
100 / 100
 456 ms 6988 KB 
//MOI Prep Set 1
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define debug(x) cout << "["<<(#x) << " -> " << (x) << "]\n";
int n, m;
vector<ll>a;
int Seg[100001 * 4];
int lz[100001 * 4];
void propagate(int k ,int l, int r){
	if (lz[k] != 0){
		Seg[k] += (r - l + 1) * lz[k];
		if (l != r){
			lz[k * 2] += lz[k];
			lz[k * 2+ 1]+=lz[k];
		}
		lz[k] = 0;
	}
}
void upd(int l1, int r1, int l = 0, int r = n - 1, int k = 1){
	propagate(k,l,r);
//	if (l1 > r1)return;
	if (l >= l1 && r <= r1){
		lz[k]++;
		propagate(k,l,r);
		return;
	}
	if (l > r1 || r < l1)return;
	upd(l1,r1,l,(l+r)/2,k*2);
	upd(l1,r1,(l+r)/2+1,r,k*2+1);
	Seg[k] = Seg[k * 2 + 1] + Seg[k * 2];
}
int val(int l1, int l = 0, int r = n - 1, int k = 1){
	propagate(k,l,r);
	if (l == r){
		return Seg[k];
	}
	int mid =(l+r)/2;
	if(l1 <= mid) return val(l1,l,(l+r)/2,k*2);
	else return val(l1,(l+r)/2+1,r,k*2+1);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    //freopen("input.txt", "r", stdin);
   //freopen("output.txt", "w", stdout);
	cin >> n >> m;
	a.resize(n);
	for (int i = 0; i < n; ++i){
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	while(m--){
		char c;
		int ci,h;
		cin >> c >> ci >> h;
		if (c == 'F'){
			int l = 0, r = n - 1, lb = n;
			while(l<=r){
				int mid = (l + r) / 2;
				if (a[mid] + val(mid) >= h){
					r = mid - 1;
					lb = mid;
				}else{
					l = mid + 1;
				}
			}
			int rb = lb + ci - 1;
			if (rb >= n-1){
				upd(lb,n-1);
				continue;
			}
			if (a[rb] + val(rb) == a[rb + 1] + val(rb + 1)){
				int kb = -1;
				l = 0, r = n - 1;
				while(l<=r){
					int mid = (l + r) / 2;
					if (a[mid] + val(mid) >= a[rb] + val(rb)){
						r = mid - 1;
						kb = mid;
					}else{
						l = mid + 1;
					}
				}
				 --kb;
				if (lb<=kb)upd(lb,kb);
				int taken = 0;
				//debug(lb);debug(kb);debug(rb);
				if (lb<=kb)taken = kb - lb + 1;
				l = 0, r = n - 1;
				kb = n;
				while(l<=r){
					int mid = (l + r) / 2;
					if (a[mid] + val(mid) > a[rb] + val(rb)){
						r = mid - 1;
						kb = mid;
					}else{
						l = mid + 1;
					}
				}
				--kb;
				upd(kb - ((rb - lb + 1) - taken) + 1, kb);
			}else{
				upd(lb,rb);
			}
		}else{
			int l = 0, r = n - 1;
			int lb = n-1;
			int rb = n - 1;
			while(l<=r){
				int mid = (l + r)/2;
				if (val(mid)+ a[mid] >=ci){
					r = mid - 1;
					lb = mid;
				}else{
					l = mid + 1;
				}
			}
			l = 0, r = n -1;
			while(l<=r){
				int mid = (l + r) / 2;
				if (val(mid)+ a[mid] > h){
					r = mid - 1;
				}else{
					l = mid + 1;
					rb = mid;
				}
			}
		//	cout<<endl;
			if (a[lb] + val(lb) >= ci && a[rb] + val(rb) <= h){
				cout<<rb - lb + 1<<'\n';
			}else{
				cout<<0<<'\n';
			}
		}
	//	cout<<endl;
		//for (int i =0 ; i < n; i++)cout<<a[i] + val(i)<<" ";
		//cout<<endl;
		
	}
	//	for (int i =0 ; i < n; i++)cout<<a[i] + val(i)<<" ";
	//	cout<<endl;

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 5416 KB Output is correct
2 Correct 346 ms 6800 KB Output is correct
3 Correct 111 ms 6732 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 4 ms 424 KB Output is correct
3 Correct 6 ms 444 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 125 ms 1596 KB Output is correct
6 Correct 177 ms 1844 KB Output is correct
7 Correct 11 ms 708 KB Output is correct
8 Correct 77 ms 1308 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 976 KB Output is correct
2 Correct 180 ms 1944 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 94 ms 1480 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 1144 KB Output is correct
2 Correct 202 ms 1940 KB Output is correct
3 Correct 23 ms 724 KB Output is correct
4 Correct 158 ms 1948 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 3056 KB Output is correct
2 Correct 413 ms 6408 KB Output is correct
3 Correct 45 ms 1876 KB Output is correct
4 Correct 90 ms 6380 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 5016 KB Output is correct
2 Correct 402 ms 5244 KB Output is correct
3 Correct 109 ms 6672 KB Output is correct
4 Correct 43 ms 1792 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 5256 KB Output is correct
2 Correct 294 ms 6544 KB Output is correct
3 Correct 102 ms 6712 KB Output is correct
4 Correct 40 ms 1868 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 5304 KB Output is correct
2 Correct 434 ms 5268 KB Output is correct
3 Correct 53 ms 5936 KB Output is correct
4 Correct 244 ms 6220 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 5372 KB Output is correct
2 Correct 301 ms 6740 KB Output is correct
3 Correct 456 ms 6988 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 5632 KB Output is correct