oj.uz

Submission #199454

# Submission time Handle Problem Language Result Execution time Memory
199454 2020-02-01T12:53:41 Z TadijaSebez Growing Trees (BOI11_grow) C++11
100 / 100
 171 ms 3448 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 2436 KB Output is correct
2 Correct 158 ms 2860 KB Output is correct
3 Correct 103 ms 2680 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 8 ms 504 KB Output is correct
3 Correct 9 ms 376 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 72 ms 1400 KB Output is correct
6 Correct 89 ms 1656 KB Output is correct
7 Correct 12 ms 504 KB Output is correct
8 Correct 50 ms 1144 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 1656 KB Output is correct
2 Correct 91 ms 1784 KB Output is correct
3 Correct 8 ms 504 KB Output is correct
4 Correct 66 ms 1400 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 1912 KB Output is correct
2 Correct 100 ms 1828 KB Output is correct
3 Correct 18 ms 504 KB Output is correct
4 Correct 90 ms 1780 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 2040 KB Output is correct
2 Correct 146 ms 2380 KB Output is correct
3 Correct 32 ms 892 KB Output is correct
4 Correct 83 ms 2304 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 2040 KB Output is correct
2 Correct 150 ms 2424 KB Output is correct
3 Correct 111 ms 2808 KB Output is correct
4 Correct 35 ms 888 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 2168 KB Output is correct
2 Correct 107 ms 2424 KB Output is correct
3 Correct 96 ms 2680 KB Output is correct
4 Correct 27 ms 888 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 2808 KB Output is correct
2 Correct 138 ms 2296 KB Output is correct
3 Correct 45 ms 1912 KB Output is correct
4 Correct 94 ms 2168 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 2604 KB Output is correct
2 Correct 152 ms 2680 KB Output is correct
3 Correct 165 ms 2936 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 3448 KB Output is correct