Submission #199454

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
199454	2020-02-01 12:53:41	TadijaSebez	Growing Trees (BOI11_grow)	C++11	100 / 100	171 ms	3448 KiB

grow

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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