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

lazypropagation
long_challenge
segment-tree
sept18

#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.


#3

Thanks i got AC :slight_smile: