Submission #717369

#	Time	Username	Problem	Language	Result	Execution time	Memory
717369		bane	Growing Trees (BOI11_grow)	C++17	100 / 100	456 ms	6988 KiB

grow

//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 / 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