oj.uz

Submission #964549

# Submission time Handle Problem Language Result Execution time Memory
964549 2024-04-17T05:40:26 Z pcc Growing Trees (BOI11_grow) C++17
0 / 100
 1000 ms 1768 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);
	for(int i = 1;i<=N+1;i++){
		assert(bit.getval(i)>=bit.getval(i-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 Execution timed out 1020 ms 1376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 960 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1053 ms 1052 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1041 ms 1084 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1016 ms 1112 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1035 ms 1112 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1054 ms 1768 KB Time limit exceeded
2 Halted 0 ms 0 KB -