oj.uz

답안 #964539

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
964539 2024-04-17T05:27:15 Z pcc Growing Trees (BOI11_grow) C++17
10 / 100
 1000 ms 3508 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){
		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;
}
int getright(int tar){
	int l = 0,r = N+1;
	while(l != r){
		int mid = (l+r)>>1;
		if(bit.getval(mid)<=tar)l = mid+1;
		else r = mid;
	}
	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 = getright(bit.getval(b))-1;
	if(a != lp){
		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);
	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]);
	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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1030 ms 1624 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Execution timed out 1079 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1036 ms 600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1008 ms 600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1022 ms 1376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1025 ms 1372 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1025 ms 1268 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 2936 KB Output is correct
2 Execution timed out 1063 ms 1372 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1020 ms 1784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 3508 KB Output is correct