fork download
copy 
  1. #include<stdio.h>
  2. #include<algorithm>
  3. #include<queue>
  4. using namespace std;
  5. int n;
  6. char a[200009];
  7. struct A{
  8.     int l,r,d;
  9.     bool operator<(const A& rhs)const{
  10.         if(r-rhs.r)return r<rhs.r;
  11.         return d>rhs.d;
  12.     }
  13. };
  14. A b[100009];
  15. int bl;
  16.  
  17. constexpr int II = 131072;
  18. int I;
  19. int ma[2*II];
  20. int getma(int dep,int ql,int qr,int ll,int rr){
  21.     if(ql<=ll&&rr<=qr)return ma[dep];
  22.     if(qr<ll||rr<ql)return 0;
  23.     return max(
  24.         getma(dep*2,ql,qr,ll,(ll+rr)/2),
  25.         getma(dep*2+1,ql,qr,(ll+rr)/2+1,rr));
  26. }
  27. void updatema(int i,int d){
  28.     i+=I;
  29.     while(i>0&&ma[i]<d){
  30.         ma[i]=d;
  31.         i>>=1;
  32.     }
  33. }
  34. int main(){
  35.     int i,j,k;
  36.     scanf("%d",&n);
  37.     scanf("%s",a);
  38.     int res=0;
  39.     for(i=0;i<n;){
  40.         if(a[i]=='1'){
  41.             i++;
  42.             continue;
  43.         }
  44.         for(j=i;j<n;j++){
  45.             if(a[j]=='1')break;
  46.         }
  47.         int l,r,d;
  48.         d=(j-i);
  49.         l=(((j+1)&(-2))>>1)-d;
  50.         r=(i&(-2))>>1;
  51.         b[bl++]={l,r,d};
  52.         i=j;
  53.     }
  54.     n>>=1;
  55.     I=1;
  56.     while(I<=n)I<<=1;
  57.     //sort(b,b+bl);
  58.     for(k=0;k<bl;k++){
  59.         for(i=b[k].l;i<=b[k].r;i++){
  60.             j=min(n,i+b[k].d);
  61. int si = max(0,i);
  62.             int dj = j-si;
  63.             int di = getma(1,0,si,0,I-1);
  64.             updatema(j,di+dj);
  65.         }
  66.         printf("%d : %d %d %d\n",k,b[k].l,b[k].r,b[k].d);
  67.         for(i=0;i<=n;i++){printf("%d ",ma[i+I]);}
  68.         printf("\n");
  69.     }
  70.  
  71.     printf("%d\n",n-ma[1]);
  72. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
18
000010000001011111
stdout
copy 
0 : -2 0 4
0 0 2 3 4 0 0 0 0 0 
1 : 0 2 6
0 0 2 3 4 0 6 6 8 0 
2 : 6 6 1
0 0 2 3 4 0 6 7 8 0 
1
https://ideone.com/krEap0
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!