Submission #717339

#	Time	Username	Problem	Language	Result	Execution time	Memory
717339		bane	Growing Trees (BOI11_grow)	C++17	0 / 100	330 ms	5348 KiB

grow

//MOI Prep Set 1
#include<bits/stdc++.h>
using namespace std;
#define ll 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);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
	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;
				}
			}
			if (lb == n)continue;
			int rb = lb + ci - 1;
			rb = min(rb, n-1);
			//debug(lb);
			//debug(rb);
			if (rb < n - 1 && val(rb) + a[rb] == val(rb+1) + a[rb + 1]){
				//edge case
				int kb = lower_bound(a.begin(), a.end(), a[rb]) - a.begin();
				kb--;
				//debug(kb);
				if(lb<=kb)upd(lb,kb);
			//	cout<<a[0]+val(0);
				int rem = rb - lb + 1 - max(0, kb - lb + 1);
				kb = upper_bound(a.begin(), a.end(), a[rb]) - a.begin();
				--kb;
			//	debug(kb);
			//	debug(kb - rem + 1);
				upd(kb - rem + 1,kb);
				
			}else{
				upd(lb,rb);
			}
		}else{
			int l = 0, r = n - 1;
			int lb = 0;
			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;
		
	}
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10