SIGSEGV in Spoj GSS1

general
, , ,
1

Hi,

I have been trying to solve GSS1 on Spoj and its giving me segmentation fault. I am not able to figure out whats the problem. Below is my code, please see if you can figure out whats the problem.

#include <iostream>
#include <algorithm>
#define MAX 500005
using namespace std;

struct data {
	long long sum, prefix_sum, suffix_sum, ans;
	data(long long val) {
		sum = val;
		prefix_sum = suffix_sum = ans = max(0LL, val);
	}
	data(long long a, long long b, long long c, long long d) : sum(a), prefix_sum(b), suffix_sum(c), ans(d) {}
	data(){}
};

data tree[4 * MAX];
long long arr[MAX];

data combine(data l, data r)
{
	data res;
	res.sum = l.sum + r.sum;
	res.prefix_sum = max(l.prefix_sum, l.sum + r.prefix_sum);
	res.suffix_sum = max(r.suffix_sum, r.sum + l.suffix_sum);
	res.ans = max(max(l.ans, r.ans), l.suffix_sum + r.prefix_sum);

	return res;
}

void build(long long node, long long tl, long long tr)
{
	if (tl > tr) return;

	if (tl == tr)
		tree[node] = data(arr[tl]);
	else {
		long long tm = (tl + tr) / 2;
		build(node * 2, tl, tm);
		build((node * 2) + 1, tm + 1, tr);

		tree[node] = combine(tree[node * 2], tree[(node * 2) + 1]);
	}
}

data query(long long node, long long tl, long long tr, long long l, long long r)
{
	if (tl > tr || r < tl || l > tr) return data(0, -1e9, -1e9, -1e9);

	if (tl <= l && r >= tr)
		return tree[node];
	
	long long tm = (tl + tr) / 2;
	data n1 = query(node * 2, tl, tm, l, r);
	data n2 = query((node * 2) + 1, tm + 1, tr, l, r);

	return combine(n1, n2);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	long long n;
	cin >> n;
	for (long long i = 0; i < n; i++)
		cin >> arr[i];

	build(1, 0, n - 1);
	long long m;
	cin >> m;
	while (m--) {
		long long x, y;
		cin >> x >> y;
		cout << query(1, 0, n - 1, x - 1, y - 1).ans << "\n";
	}

	return 0;
}

PS: Got AC.!! (tl <= l && r >= tr) should be (tl >= l && tr <= r)

1 Like