oj.uz

Submission #964550

# Submission time Handle Problem Language Result Execution time Memory
964550 2024-04-17T05:40:55 Z pcc Growing Trees (BOI11_grow) C++17
10 / 100
 86 ms 1568 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 1e5+10;

struct BIT{
	int bit[mxn];
	void modify(int p,int v){
		if(!p)p = 1;
		for(;p<mxn;p+=p&-p)bit[p] += v;
		return;
	}
	int getval(int p){
		int re = 0;
		for(;p>0;p-= p&-p)re += bit[p];
		return re;
	}
};

int arr[mxn];
int N,Q;
BIT bit;

int getleft(int tar){
	int l = 0,r = N+1;
	while(l != r){
		int mid = (l+r)>>1;
		if(bit.getval(mid)>=tar)r = mid;
		else l = mid+1;
	}
	return l;
}

void add(int a,int b){
	a= getleft(a);
	b = min(N,a+b-1);
	if(a>N)return;
	int lp = getleft(bit.getval(b));
	int rp = getleft(bit.getval(b)+1)-1;
	assert(a<=lp&&lp<=rp&&lp<=b);
	bit.modify(a,1);
	bit.modify(lp,-1);
	int len = b-lp+1;
	bit.modify(rp-len+1,1);
	bit.modify(rp+1,-1);
	return;
}

int btw(int a,int b){
	int ta = getleft(a);
	int tb = getleft(b+1);
	assert(tb>=ta);
	return tb-ta;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	for(int i = 1;i<=N;i++)cin>>arr[i];
	sort(arr+1,arr+N+1);
	for(int i = 1;i<=N;i++)bit.modify(i,arr[i]-arr[i-1]);
	bit.modify(N+1,(int)1e9);
	while(Q--){
		char t;
		int a,b;
		cin>>t>>a>>b;
		if(t == 'F')add(b,a);
		else cout<<btw(a,b)<<'\n';
	}
	return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 2 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 37 ms 760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 1204 KB Output is correct
2 Incorrect 69 ms 1136 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

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

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 1568 KB Output is correct