Help me in the "AND Square Subsegments" problem (codechef long challenge).

general
, , ,
1

By reading the editorial i wrote my code using segment tree with lazy propagation but on submitting i am getting AC on 2 test cases and TLE on remaining :frowning: I am getting TLE even in the first subtask.

I checked my code by taking test cases of order n=10^3 , q=10^3 and in all those test cases my code is working fine.

Please anyone help me to get rid over it. That will be of great help indeed.

My solution — link

problem Link- link

2

While finding the next group index, we won’t see the next change index over zero bits of a number because zero bits are anyway not going to change.

So the next change index should be the minimum of next change indexes over the one bits of a number.

So this code snippet on line 183:


for(j=0;j<=30;j++) 
    {
     mn=min(mn,dp[j][z]);
    }

Will change to:


    for(j=0;j<=30;j++) 
    {
      if( (1 << j) & val)
         mn=min(mn,dp[j][z]);
    }

You can have a look at my upsolved solution.

1 Like
3

Thanks i got AC :slight_smile: