This is one of the famous Interval tree problems, I think many of you solved it at some point of you competition career. The problem is this:

Can you answer this Queries V

Below is my solution — it is not perfect obviously, but with similar code I already solved GSS1 and GSS3:

Can you answer this Queries I Can you answer this Queries III

So it is partially tested and AC'ed. The problem I encountered — under Miscrosoft Visual Studio Express 2013 it compiles and works fine in debug mode. I tried preparing random test cases for it and none of the runs I did (several thousand random testcases) could replicate the problem.

SPOJ reponse to this code is always the same — SIGABRT or SIGSERV, randomly. I understand that for SIGSERV I should be looking for writing outside of boundaries of array, but solution uses only vectors and it should be detected in debug mode... Maybe I was not able to replicate that single specific testcase which leads to the problem.

Can anybody please provide any clues?

Thanks,

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <cassert>

using namespace std;

struct entry
{
	entry() : sum(0), best(0), left(0), right(0) {};
	entry(int value) : sum(value), best(value), left(value), right(value) {};
	entry(int v1, int v2, int v3, int v4) : sum(v1), best(v2), left(v3), right(v4) {};

	int best;
	int sum;
	int left;
	int right;
};

vector<vector<entry>> M;


entry getValue(int a, int b, int depth, int s = 0)
{
	if (a > b) return entry(0);

	int left = (1 << depth) * s;
	int right = (1 << depth) * (s + 1) - 1;

	if (a == left && b == right) return M[depth][s];

	int mid = (left + right) / 2;

	if (a <= mid && b <= mid) return getValue(a, b, depth - 1, 2 * s);
	if (a > mid && b > mid) return getValue(a, b, depth - 1, 2 * s + 1);

	entry Left = getValue(a, mid, depth - 1, s * 2);
	entry Right = getValue(mid + 1, b, depth - 1, s * 2 +1);

	return entry(Left.sum + Right.sum, max(max(Left.best, Right.best), Left.right + Right.left), max(Left.left, Left.sum + Right.left), max(Right.right, Right.sum + Left.right));
}

int main()
{
	int t;

	cin >> t;

	while (t--)
	{

		ios_base::sync_with_stdio(0);

		int n;
		cin >> n;

		M = vector<vector<entry>>();

		M.push_back(vector<entry>(n));

		for (int i = 0; i < n; i++)
		{
			int t;
			cin >> t;

			M[0][i] = t;
		}

		int k = n;
		int depth = 0;

		while (k > 0)
		{
			depth++;
			M.push_back(vector<entry>(k / 2 + 2));

			for (int i = 0; i < M[depth - 1].size(); i += 2)
			{
				if (i + 1 == M[depth - 1].size())
				{
					M[depth][i / 2].sum = M[depth - 1][i].sum;
					M[depth][i / 2].best = M[depth - 1][i].best;
					M[depth][i / 2].left = M[depth - 1][i].left;
					M[depth][i / 2].right = 0;
				}
				else
				{
					M[depth][i / 2].sum = M[depth - 1][i].sum + M[depth - 1][i + 1].sum;
					M[depth][i / 2].left = max(M[depth - 1][i].left, M[depth - 1][i].sum + M[depth - 1][i + 1].left);
					M[depth][i / 2].right = max(M[depth - 1][i + 1].right, M[depth - 1][i + 1].sum + M[depth - 1][i].right);
					M[depth][i / 2].best = max(max(M[depth - 1][i].best, M[depth - 1][i + 1].best), M[depth - 1][i].right + M[depth - 1][i + 1].left);
				}
			}

			k = k / 2;
		}

		int q;
		cin >> q;

		while (q--)
		{
			int x1, x2, y1, y2;
			cin >> x1 >> y1 >> x2 >> y2;
			x1--, y1--, x2--, y2--;

			int ans;
			if (y1 < x2)
			{
				entry Middle = getValue(y1 + 1, x2 - 1, depth);
				entry Left = getValue(x2, y2, depth);
				entry Right = getValue(x1, y1, depth);

				ans = Left.left + Right.right + Middle.sum;
			}
			else
			{
				int Middle = getValue(x2, y1, depth).best;

				int l1 = getValue(x1, x2, depth).right;
				int r1 = getValue(x2 + 1, y2, depth).left;
				l1 = max(l1, l1 + r1);

				int r2 = getValue(y1 + 1, y2, depth).left;
				int l2 = getValue(x1, y1, depth).right;
				l2 = max(l2, l2 + r2);

				ans = max(Middle, max(l1, l2));
			}

			cout << ans << "\n";

		}

	}
}