oj.uz

Submission #964553

# Submission time Handle Problem Language Result Execution time Memory
964553 2024-04-17T05:45:25 Z pcc Growing Trees (BOI11_grow) C++17
100 / 100
 104 ms 2996 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 = 1,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);
	assert(bit.getval(lp) == bit.getval(rp)&&bit.getval(lp) == bit.getval(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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 1308 KB Output is correct
2 Correct 87 ms 2644 KB Output is correct
3 Correct 62 ms 2868 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 38 ms 1368 KB Output is correct
6 Correct 45 ms 1732 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 22 ms 1304 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 788 KB Output is correct
2 Correct 51 ms 1876 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 35 ms 1356 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 848 KB Output is correct
2 Correct 63 ms 1840 KB Output is correct
3 Correct 5 ms 600 KB Output is correct
4 Correct 51 ms 1724 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 1044 KB Output is correct
2 Correct 87 ms 2440 KB Output is correct
3 Correct 15 ms 856 KB Output is correct
4 Correct 45 ms 2292 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 1104 KB Output is correct
2 Correct 84 ms 2412 KB Output is correct
3 Correct 51 ms 2676 KB Output is correct
4 Correct 14 ms 860 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 1272 KB Output is correct
2 Correct 54 ms 2520 KB Output is correct
3 Correct 56 ms 2628 KB Output is correct
4 Correct 13 ms 860 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 1184 KB Output is correct
2 Correct 87 ms 1188 KB Output is correct
3 Correct 22 ms 1896 KB Output is correct
4 Correct 46 ms 2212 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 1268 KB Output is correct
2 Correct 87 ms 2672 KB Output is correct
3 Correct 87 ms 2996 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 1556 KB Output is correct