SPOJ-LITE question

I’m not able to find any wrong in my code for the question : http://www.spoj.com/problems/LITE/,
this is my code:

#include

using namespace std;

int n,m;

struct tree
{
int flag,sum;
};
tree seg[500000];
int lazy[500000]={0};

void build_tree(int pos,int low,int high)
{
if(low==high)
{
seg[pos].flag=seg[pos].sum=0;
return;
}
int mid=(low+high)/2;
build_tree(2pos+1,low,mid);
build_tree(2
pos+2,mid+1,high);
seg[pos].flag=seg[2pos+1].flag||seg[2pos+2].flag;
seg[pos].sum=seg[2pos+1].sum+seg[2pos+2].sum;

}
void update(int pos,int low,int high,int l,int r)
{

if(lazy[pos]==-1)
{
    seg[pos].flag^=1;
    seg[pos].sum=(high-low+1)*(seg[pos].flag);
    if(low!=high)
    {
        lazy[2*pos+1]=-1;
        lazy[2*pos+2]=-1;
    }
    lazy[pos]=0;
}


if(low>r||high<l)
    return;

if(low>=l&&high<=r)
{
    seg[pos].flag^=1;
    seg[pos].sum=(high-low+1)*(seg[pos].flag);
    if(low!=high)
    {
        lazy[2*pos+1]=-1;
        lazy[2*pos+2]=-1;
    }
    return;
}

int mid=(low+high)/2;
update(2*pos+1,low,mid,l,r);
update(2*pos+2,mid+1,high,l,r);
seg[pos].flag=seg[2*pos+1].flag||seg[2*pos+2].flag;
seg[pos].sum=seg[2*pos+1].sum+seg[2*pos+2].sum;

}

int query(int pos,int low,int high,int l,int r)
{
if(low>r||high<l)
return 0;
if(lazy[pos]==-1)
{
seg[pos].flag^=1;
seg[pos].sum=(high-low+1)(seg[pos].flag);
if(low!=high)
{
lazy[2
pos+1]=-1;
lazy[2*pos+2]=-1;
}
lazy[pos]=0;
}
if(low>=l&&high<=r)
return(seg[pos].sum);

int mid=(low+high)/2;
int p1=query(2*pos+1,low,mid,l,r);
int p2=query(2*pos+2,mid+1,high,l,r);
return (p1+p2);

}
int main()
{

cin>>n>>m;
int x,y,z;
build_tree(0,0,n-1);
while(m–)
{
cin>>x>>y>>z;
if(x==0)
{
update(0,0,n-1,y-1,z-1);
}
else
{
cout<<query(0,0,n-1,y-1,z-1)<<endl;
}

    //for(int i=0;i<8;i++)
      //  cout<<i<<" "<<seg[i].flag<<" "<<seg[i].sum<<" lazy "<<lazy[i]<<endl;

}
}

I think your test code is failing here-

Compilation Successful
Input (stdin)
4 4
0 1 4
0 1 2
0 1 4
1 1 4
Your Output
0

My expected output is 2.
1st query==> Lights 1,2,3,4 switched on.
2nd query ==> lights 1,2 switched off
3rd query ===>Lights 1,2 switched on while 3,4 switched off

That’s how my understanding of the Q goes, (might be wrong kindly confirm :slight_smile: )

1 Like

This is the corrected code. Your method of updation was wrong. What you were doing is that either the complete interval in segment tree will store answer 0, or it will store the size of that interval. This causes problems when at the time of updation, you merge two intervals, one having no switch ON (therefore answer 0) and the other having all switches ON(answer equal to length of that interval). In that case answer is the sum of the answers of the two intervals being merged. However your code make it so that the ‘flag’ you use, interprets that merged interval as one which as ALL switches ON. This is wrong.

In fact, you don’t even need to use any ‘flag’. Just make sure at the time of updation, answer stored by a node = length of interval - answer stored in that node, thereby making sure that in an update the ON switches were turned OFF and OFF turned ON. I didn’t remove the ‘flag’ from the corrected code. Read it up to make sure that ‘flag’ plays no role here.

If you feel your question was answered, please mark this answer as ‘Accepted’.

3 Likes

@kashyap2108

I realized there was another mistake in your code. You weren’t keeping track of how many times you had to perform lazy updates. I did that, and it works fine now. You just kept track of whether to update or not. We also need to know how many times to perform update.

Tell me if you face any other problem.

Link - http://ideone.com/WuLOZV

is there any link to your code on ideone.com or etc. ? Cant copy paste your code to test.

1 Like

please don’t paste your solution here like this. It make us cumbersome to grasp the words properly. Always try to paste the link after compiling on ideone.com like platform

2 Likes

Yes, thats exactly why his code fails in my test case,

Thanks!!! to all

stdin
4 4
0 1 4
0 3 4
1 3 3
1 4 4

stdout

1
1
The output should be 0 and 0

@kashyap2108 read my new answer

Thanks!!got it!!