Submission #711564

#	Time	Username	Problem	Language	Result	Execution time	Memory
711564		Pherokung	Growing Trees (BOI11_grow)	C++14	100 / 100	273 ms	2848 KiB

grow

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define F first
#define S second
int n,m,a[MAXN],x,y,fen[MAXN*8],l,r,l2,r2;
char ch[5];

void update(int pos,int v){
	for(;pos<=n;pos+=(pos&(-pos))) fen[pos] += v;
}

int query(int pos){
	int sum = 0;
	for(;pos>0;pos-=(pos&(-pos))) sum += fen[pos];
	return sum;
}

pair<int,int> find_bound(int v){
	int be,ed,mid,l,r;
	
	be = 1, ed = n;
	while(be <= ed){
		mid = (be+ed)/2;
		if(query(mid) < v) be = mid+1;
		else ed = mid-1;
	}
	l = be;
	
	be = 1, ed = n;
	while(be <= ed){
		mid = (be+ed)/2;
		if(query(mid) <= v) be = mid+1;
		else ed = mid-1;
	}
	r = ed;
	return {l,r};
}

void debug(){
	printf("========\n");
	for(int i=1;i<=n;i++) printf("%d ",query(i));
	printf("\n========\n");
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++) update(i,a[i]-a[i-1]);
	
	//debug();
	for(int i=1;i<=m;i++){
		scanf("%s%d%d",ch,&x,&y);
		if(ch[0] == 'F'){
			l = find_bound(y).F;
			r = min(l + x - 1, n);
			if(query(r) != query(r+1) || r == n) update(l,1), update(r+1,-1);
			else{
				pair<int,int> LR2 = find_bound(query(r));
				l2 = LR2.F, r2 = LR2.S;
				update(l,1), update(l2,-1);
				update(r2-(x-(l2-l))+1,1), update(r2+1,-1);
				//printf("??? %d %d , %d %d : %d\n",l,r,l2,r2,r2-(x-(l2-l))+1);
			}
		}
		else{
			l = find_bound(x).F;
			r = find_bound(y).S;
			printf("%d\n",r-l+1);
		}
		//debug();
	}
}

Compilation message (stderr)

grow.cpp: In function 'int main()':
grow.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
grow.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |   scanf("%d",&a[i]);
      |   ~~~~~^~~~~~~~~~~~
grow.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   scanf("%s%d%d",ch,&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10