Submission #199454

#	Time	Username	Problem	Language	Result	Execution time	Memory
199454		TadijaSebez	Growing Trees (BOI11_grow)	C++11	100 / 100	171 ms	3448 KiB

grow

#include <bits/stdc++.h>
using namespace std;
const int N=100050;
int bit[N];
void Add(int i,int f){for(;i<N;i+=i&-i)bit[i]+=f;}
void Add(int l,int r,int f){Add(l,f);Add(r+1,-f);}
int Get(int i){int ans=0;for(;i;i-=i&-i)ans+=bit[i];return ans;}
int a[N];
int main(){
	int n,m;
	scanf("%i %i",&n,&m);
	for(int i=1;i<=n;i++)scanf("%i",&a[i]);
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++)Add(i,i,a[i]);
	while(m--){
		char t;
		scanf("\n%c",&t);
		if(t=='F'){
			int c,h;
			scanf("%i %i",&c,&h);
			int top=n,bot=1,mid,ans=n+1;
			while(top>=bot){
				mid=top+bot>>1;
				if(Get(mid)>=h)ans=mid,top=mid-1;
				else bot=mid+1;
			}
			int L=ans,R=min(n,ans+c-1);
			top=R,bot=1;
			int le=R;
			while(top>=bot){
				mid=top+bot>>1;
				if(Get(mid)==Get(R))le=mid,top=mid-1;
				else bot=mid+1;
			}
			top=n,bot=R;
			int ri=R;
			while(top>=bot){
				mid=top+bot>>1;
				if(Get(mid)==Get(R))ri=mid,bot=mid+1;
				else top=mid-1;
			}
			Add(L,le-1,1);
			Add(le+ri-R,ri,1);
		}
		else{
			int l,r;
			scanf("%i %i",&l,&r);
			int top=n,bot=1,mid,L=n+1;
			while(top>=bot){
				mid=top+bot>>1;
				if(Get(mid)>=l)L=mid,top=mid-1;
				else bot=mid+1;
			}
			top=n,bot=1;
			int R=0;
			while(top>=bot){
				mid=top+bot>>1;
				if(Get(mid)<=r)R=mid,bot=mid+1;
				else top=mid-1;
			}
			printf("%i\n",R-L+1);
		}
	}
	return 0;
}

Compilation message (stderr)

grow.cpp: In function 'int main()':
grow.cpp:23:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     mid=top+bot>>1;
         ~~~^~~~
grow.cpp:31:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     mid=top+bot>>1;
         ~~~^~~~
grow.cpp:38:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     mid=top+bot>>1;
         ~~~^~~~
grow.cpp:50:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     mid=top+bot>>1;
         ~~~^~~~
grow.cpp:57:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     mid=top+bot>>1;
         ~~~^~~~
grow.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
grow.cpp:12:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++)scanf("%i",&a[i]);
                       ~~~~~^~~~~~~~~~~~
grow.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("\n%c",&t);
   ~~~~~^~~~~~~~~~~
grow.cpp:20:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%i %i",&c,&h);
    ~~~~~^~~~~~~~~~~~~~~
grow.cpp:47:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%i %i",&l,&r);
    ~~~~~^~~~~~~~~~~~~~~

• 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