Getting SIGSEGV error in FLIPCOIN

help
, , , ,
1

Problem Link : FLIPCOIN Problem - CodeChef

I have tried this problem by making use of segment trees and I can pass all the test cases too, but when I tried to submit my code it said SIGSEGV error.

Here’s my code:

#include <bits/stdc++.h>
using namespace std;

void buildTree(int *arr, int *tree, int startIndex, int endIndex, int start){
    
    //base case
    if(startIndex == endIndex){
        tree[start] = arr[startIndex];
        return;
    }
    
    //recursive call
    int mid = (startIndex + endIndex)/2;
    buildTree(arr, tree, startIndex, mid, 2 * start + 1);
    buildTree(arr, tree, mid + 1, endIndex, 2 * start + 2);
    tree[start] = tree[2 * start + 1] + tree[2 * start + 2];
}

int query(int *tree, int left, int right, int startIndex, int endIndex, int start){
    
    //total overlap
    if(left <= startIndex && right >= endIndex) return tree[start];
    
    //no overlap
    if(left > endIndex || right < startIndex) return 0;
    
    //partial overlap
    int mid = (startIndex + endIndex)/2;
    return query(tree, left, right, startIndex, mid, 2 * start + 1) + query(tree, left, right, mid + 1, endIndex, 2 * start + 2);
}

void update(int *tree, int left, int right, int startIndex, int endIndex, int start){
    
    //not in bounds
    if(left > endIndex || right < startIndex) return;
    
    //base case
    if(startIndex == endIndex){
        tree[start] = tree[start] == 1 ? 0 : 1;
		return;
    }
    
    //recursive calls
    int mid = (startIndex + endIndex)/2;
    update(tree, left, right, startIndex, mid, 2 * start + 1);
    update(tree, left, right, mid + 1, endIndex, 2 * start + 2);
    
    tree[start] = tree[2 * start + 1] + tree[2 * start + 2];
}

int main() {
	// your code goes here
	int n, c;
	cin>>n>>c;
	int arr[n];
	memset(arr, 0, sizeof(arr));

    int *tree = new int[2 * n - 1];

    buildTree(arr, tree, 0, n - 1, 0);
	int q[3];
	while(c--){
		for(int i = 0; i<3; i++) cin>>q[i];
		if(q[0] == 1) cout<<query(tree, q[1], q[2], 0, n - 1, 0)<<endl;
		else update(tree, q[1], q[2], 0, n - 1, 0);
	}
	delete tree;
	return 0;
}

Somebody, pls help me out and thanks in advance :slight_smile:

2

From what i can remember we have to use lazy propagation in this problem. I cannot say much about the error you are getting.

3

tree size should be more than 4*n+1.

2 Likes
4

Thanks a lot, it worked but as far as I remember, the tree size should be (2 * n - 1), why did it didn’t work for that much size?

5
6

Thanks a lot, and I got AC for that question. Thanks for your time.

1 Like