Substring

• Problem Description

  
  "You are given a string S of length N consisting only of 0s and 1s. You are also given an integer K.You have to answer Q queries. In the ith query, two integers Li and Ri are given. Then you should print the number of substrings of S[L, R] which contain at most K 0s and at most K 1s where S[L, R] denotes the substring from Lth to Rth characters of the string S. 
  In other words, you have to count number of pairs (i, j) of integers such that L i j R such that no character in substring S[i, j] occurs more than K times.
  "
  

• CODING ARENA

• #include<stdio.h>

  #define gc getchar_unlocked()

  char str[100005];

  void getstring()

  {int i=0;

   char ch=gc;

   while(ch<'0')

   ch=gc;

   while(ch>='0')

   {str[i++]=ch;

    ch=gc;

   }

  }

  int getn()

  { int i=0;

    char ch=gc;

    while(ch<'0'||ch>'9')

    ch=gc;

    while(ch<='9'&&ch>='0')

    { i=(i<<1)+(i<<3)+ch-'0';

      ch=gc;

    }

  return i;

  }

  int main()

  {int t,n,k,q,i,l,r,m,x,y,zero,one;

   long long int ans,a,b;

   int ra[100005];

   int abc[100005];

   long long int sum[100005];

   t=getn();

   while(t--)

   {   

        n=getn();k=getn();q=getn();

        getstring();

        l=1;

        r=n;

        one=0;zero=0;m=l-2;

             ans=0;

             for(i=l-1;i<r;i++)

             {  

                if(str[m+1]=='1')

                {x=1;y=0;}

                else

                {x=0;y=1;

                }

                while((m+1)<r&&((zero+y)<=k&&(one+x)<=k))

                {  zero=zero+y;

                   one=one+x;

                   m++;

                   if(str[m+1]=='1')

                   {x=1;y=0;}

                   else

                   { x=0;y=1;

                   }

                }

                a=m-i+1;

                abc[i]=a;

                if(str[i]=='1')

                one--;

                else

                zero--;

             }

        sum[0]=0;

        for(i=1;i<=n;i++)           

        sum[i]=sum[i-1]+abc[i-1];

        /*for(i=0;i<n;i++)

        printf("%d ",abc[i]);     

        */   

        for(i=0;i<1;i++)

          { if(abc[i]>(1-i))

            break;

          }

          ra[1]=i;

        for(r=2;r<=n;r++)

        { for(i=ra[r-1];i<r;i++)

          { if(abc[i]>(r-i))

            break;

          }

          ra[r]=i;

        }

        while(q--)

        {    l=getn();r=getn();

             ans=0;

                /*for(i=l-1;i<r;i++)

               {if(abc[i]>(r-i))

                 break;

               

                 //printf("%lld",ans);

               }

                */ if(l-1<ra[r])

                   {ans+=(sum[ra[r]]-sum[l-1]);

                   a=(r-ra[r]);

                   b=(r-ra[r]+1);

                   ans+=a*b/2;

                    }

                    else

                    { a=(r-l+1);

                      b=(r-l+2); 

                      ans=a*b/2;

                     }

                   

                       printf("%lld\n",ans);

        }

   }

   return 0; 

  }

• Test Case 1

  
  Input (stdin)

  1
  
  8 2 3
  
  01110000
  
  1 4
  
  2 4
  
  5 8
  
  

  Expected Output

  8
  
  5
  
  7

• Test Case 2

  
  Input (stdin)

  1
  
  8 2 3
  
  11111000
  
  1 5
  
  2 5
  
  5 8
  
  

  Expected Output

  9
  
  7
  
  8