Here is the problem link - https://www.codechef.com/problems/FLIPCOIN
Ideone link for my solution - http://ideone.com/fhJYGT
I am getting similar errors on the other problems related to segment tree that I’ve tried.I don’t know what it is though I tried hard to figure it out. Please help me by looking at my code and telling me where am I going wrong and what can be done to correct it .I know what a SIGSEGV error is.
Here's my code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int *seg,*lazy;int n,q;
int arr[100005];
void build(int low , int high , int pos)
{
if(low==high)seg[pos] = arr[low];
else
{
int mid = (low+high)>>1;
build(low , mid , pos<<1);
build(mid+1 , high , (pos<<1)+1);
seg[pos] = seg[pos<<1] + seg[2*pos+1];
}
}
void update(int low , int high , int qlow , int qhigh , int pos)
{
if(lazy[pos]==1){
seg[pos] = (high-low+1) - seg[pos];
if(low!=high)
{
lazy[pos>>1] = 1-lazy[pos>>1];
lazy[2*pos+1] = 1 - lazy[2*pos+1];
}
lazy[pos] = 0;
}
if(qlow>high ||qhigh<low)return; //NO OVERLAP
if(low<=qlow && high<=qhigh)
{
seg[pos] = (high - low +1) - seg[pos];
if(low!=high)
{
lazy[pos<<1] = 1-lazy[pos<<1];
lazy[2*pos+1] = 1-lazy[2*pos+1];
}
return;
}
int mid = (low+high)>>1;
update(low , mid , qlow , qhigh , pos<<1);
update(mid+1 , high , qlow , qhigh , 2*pos+1);
seg[pos] = seg[pos<<1]+seg[2*pos+1];
}
int query(int low , int high , int qlow , int qhigh , int pos)
{
if(qlow>high || qhigh<low)return 0;
if(lazy[pos]==1){
seg[pos] = (high -low+1) - seg[pos];
if(low!=high){
lazy[pos<<1] = 1-lazy[pos<<1];
lazy[2*pos+1] = 1-lazy[2*pos+1];
}
lazy[pos] = 0;
}
if(low>=qlow && high<=qhigh)return seg[pos];
int mid = (low+high)>>1;
int sum1 = query(low , mid , qlow , qhigh , pos<<1);
int sum2 = query(mid+1 , high , qlow , qhigh , 2*pos+1);
return sum1+sum2;
}
void initseg(){
int ht = ceil(log2(n)),i;
int size = (pow(2,ht)*2)+5;
seg = new int[size];
lazy= new int[size];
for(i=0;i<size;i++){
seg[i] = 0;
lazy[i] =0;
}
}
int main(){
cin>>n>>q;
initseg();
while(q--){
int op , a , b;
cin>>op>>a>>b;
if(!op){
update(0 , n-1 , a , b , 1);
}
else
{
cout<<query(0 , n-1 , a, b , 1)<<endl;
}
}
return 0;
}