oj.uz

Submission #941534

# Submission time Handle Problem Language Result Execution time Memory
941534 2024-03-09T05:46:40 Z tamir1 Growing Trees (BOI11_grow) C++17
0 / 100
 402 ms 4128 KB 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,i,x,y,a[100005],s[400005];
char type;
void build(ll node,ll l,ll r){
	if(l==r){
		s[node]=a[l];
		return;
	}
	ll mid=(r+l)/2;
	build(node*2,l,mid);
	build(node*2+1,mid+1,r);
}
ll get(ll node,ll l,ll r,ll loc){
	if(l>loc || r<loc) return 0;
	if(r==l) return s[node];
	ll mid=(r+l)/2;
	return s[node]+get(node*2,l,mid,loc)+get(node*2+1,mid+1,r,loc);
}
ll find(ll x,ll y){
	if(get(1,1,n,1)>y || get(1,1,n,n)<x) return 0;
	ll l1=1,r1=n,l2=1,r2=n;
	while(r1-l1>1){
		ll mid=(l1+r1+1)/2;
		if(get(1,1,n,mid)<x) l1=mid;
		else r1=mid;
	}
	if(get(1,1,n,l1)<x) l1=r1;
	while(r2-l2>1){
		ll mid=(r2+l2+1)/2;
		if(get(1,1,n,mid)>y) r2=mid;
		else l2=mid;
	}
	if(get(1,1,n,r2)>y) r2=l2;
	return r2-l1+1;
}
void update(ll node,ll l,ll r,ll L,ll R){
	if(l>R || r<L) return;
	if(l>=L && r<=R){
		s[node]++;
		return;
	}
	ll mid=(r+l)/2;
	update(node*2,l,mid,L,R);
	update(node*2+1,mid+1,r,L,R);
}
void change(ll c,ll h){
	ll l=1,r=n;
	if(get(1,1,n,n)<h) return;
	while(r-l>1){
		ll mid=(r+l+1)/2;
		if(get(1,1,n,mid)<h) l=mid;
		else r=mid;
	}
	if(get(1,1,n,l)<h) l=r;
	if(l+c-1>=n){
		update(1,1,n,l,n);
		return;
	}
	r=l+c-1;
	ll val=get(1,1,n,r);
	ll l1=1,r1=n;
	while(r1-l1>1){
		ll mid=(r1+l1+1)/2;
		if(get(1,1,n,mid)>=val) r1=mid;
		else l1=mid;
	}
	if(r1>=val) r1=l1;
	update(1,1,n,l,r1);
	c=c-(r1-l+1);
	l=1;
	r=n;
	while(r-l>1){
		ll mid=(r+l+1)/2;
		if(get(1,1,n,mid)<=val) l=mid;
		else r=mid;
	}
	if(get(1,1,n,r)>val) r=l;
	update(1,1,n,r-c+1,r);
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(i=1;i<=n;i++) cin >> a[i];
	sort(a+1,a+n+1);
	build(1,1,n);
	while(m--){
		cin >> type >> x >> y;
		if(type=='C'){
			cout << find(x,y) << "\n";
		}
		else{
			change(x,y);
		}
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 3452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Incorrect 5 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 173 ms 940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 244 ms 3296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 311 ms 3408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 3164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 402 ms 3416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 307 ms 3468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 371 ms 4128 KB Output isn't correct
2 Halted 0 ms 0 KB -