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:
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";
}
}
}
Can you please paste your code somewhere here: http://everfall.com/paste http://ideone.com ?
About the bug:
What if
x2 == y2
?Thank you!
Source
It doesn't work on ideone, so I should be ok going forward — I can debug something which doesn't work. I was frustrated because it did work seamlessly in Visual C++.
Case where x2 == y2 should be theoretically covered by
if (a > b) return entry(0);
but bug is definitely somewhere around lines 123-144.