 # Spoj GSS1 problem

But the point is that I am not getting TLE. I am getting WA.

That’s strange. This is your code, right? http://ideone.com/H2wjUT
This was giving TLE, so I made the changes I just told you about, and the result was AC.

3 Likes

OK got AC. Thanks everyone for helping.

1 Like

That WA was coming because I had commented some part and didn’t realize it.

1 Like

@mathecodician, @meooow is never wrong 1 Like

@meooow = ShaktiBilli (I call him that)   XD

2 Likes

@meooow for the ans of any query we are checking if (l > mid) or if (r <= mid) why are we doing this check below i have added the sample code

`if (l > mid) return query(2*index+2, mid+1, end, l, r);`
In this part if l>mid, then values below mid are irrelevant so we check for values only above mid, ie, mid+1 to end. And if l>mid then r must be greater than mid.

`if (r <= mid) return query(2*index+1, start, mid, l, r);`
In this part r<=mid so values above mid are irrelevant. And if r<=mid then l must be below r and hence below mid.

You can match this idea to that of binary search, in terms, that we are discarding irrelevant positions ie, positions that won’t affect our query or computation.

1 Like

but if i am removing these two lines code is giving me the wrong answer

If you remove that part of code you need to use

`node left = query(2*index+1,start,mid,l,min (mid,r)); node right = query(2*index+2,mid+1,end,max(l,mid+1),r);`

This should work, though I don’t use it coz it may be prone to error sometimes

can you explain why…i am very confused with this

http://e-maxx.ru/algo/segment_tree This link explains this, though I’ve implemented this way but it gives WA in test case 9 probably we need to take care of edge cases

1 Like

can anybody tell why it is giving wrong answer if i remove line number 70 to 73

see if i remove that line number 70 to 73 its giving wrong answer…why?

Awesome! Thankyou so much!

Can somebody tell me why I am getting WA for test case 9?

I have done it like this but it is giving a wrong answer on test case 9
Can somebody please check where I am making a mistake?

#include <bits/stdc++.h>
#include
typedef long long ll;
using namespace std;
struct total
{
ll actual_sum;
ll prefix_sum;
ll suffix_sum;
ll sum;
};
void build_tree(ll arr,total tree,int node,int start,int end)
{
if(start==end)
{
tree[node].suffix_sum=arr[start];
tree[node].prefix_sum=arr[start];
tree[node].actual_sum=arr[start];
tree[node].sum=arr[start];
return;
}
int mid=(start+end)/2;
build_tree(arr,tree,node
2,start,mid);
build_tree(arr,tree,node
2+1,mid+1,end);
ll maximum=max(maximum,tree[node2].suffix_sum+tree[node2+1].prefix_sum);
maximum=max(maximum,max(tree[node2].sum+tree[node2+1].prefix_sum,tree[node2+1].sum+tree[node2].suffix_sum));
tree[node].actual_sum=maximum;
tree[node].prefix_sum=max(tree[node2].prefix_sum,tree[node2].sum+tree[node2+1].prefix_sum);
tree[node].suffix_sum=max(tree[node
2+1].suffix_sum,tree[node2+1].sum+tree[node2].suffix_sum);
tree[node].sum=tree[node2+1].sum+tree[node2].sum;
return;
}
total ans(total tree,int node,int start,int end,int left ,int right)
{
if(start>right || end<left)
{
total t1;
t1.prefix_sum=-100000;
t1.suffix_sum=-100000;
t1.actual_sum=-100000;
t1.sum=-100000;
return t1;
}
if(start>=left && end<=right)
return tree[node];
else
{
int mid=(start+end)/2;
if(mid<left)
return ans(tree,node
2+1,mid+1,end,left,right);
if(mid>=right)
return ans(tree,node2,start,mid,left,right);
total t1=ans(tree,node
2,start,mid,left,right);
total t2=ans(tree,node2+1,mid+1,end,left,right);
total t3;
ll maximum=max(t1.actual_sum,t2.actual_sum);
maximum=max(maximum,t1.suffix_sum+t2.prefix_sum);
t3.actual_sum=maximum;
t3.prefix_sum=max(t1.prefix_sum,t1.sum+t2.prefix_sum);
t3.suffix_sum=max(t2.suffix_sum,t2.sum+t1.suffix_sum);
t3.sum=t2.sum+t1.sum;
return t3;
}
}
int main() {
int n;
cin>>n;
ll arr[n];
total tree[4
n];
for(int i=0;i<n;i++)
cin>>arr[i];
build_tree(arr,tree,1,0,n-1);
int q;
cin>>q;
while(q–)
{
int a,b;
cin>>a>>b;
cout<<ans(tree,1,0,n-1,a-1,b-1).actual_sum<<endl;
}
return 0;
}

1 Like

Please format your code using preformatted text. It has a sign like </> just above the tab where you write.
Also you can see my accepted solution (if you want to) below:

Accepted Solution
``````#include <bits/stdc++.h>
using namespace std;
const long long N = 1000010;
long long a[N];

struct define {
long long prefix, middle, suffix, all;
};

vector<define> seg(N * 2);

define UpdatePosition(define seg1, define seg2) {
define ori;
ori.all = seg1.all + seg2.all;
ori.prefix = max(seg1.prefix, max(seg1.all + seg2.prefix, ori.all));
ori.suffix = max(seg2.suffix, max(seg2.all + seg1.suffix, ori.all));
ori.middle = max(seg1.suffix + seg2.prefix, max(seg1.middle, seg2.middle));
return ori;
}

void Construct(long long l, long long r, long long pos) {
long long mid = (l + r) / 2;
if(l == r) {
seg[pos].prefix = a[l];
seg[pos].middle = a[l];
seg[pos].suffix = a[l];
seg[pos].all = a[l];
return;
}
Construct(l, mid, pos * 2);
Construct(mid + 1, r, pos * 2 + 1);
seg[pos] = UpdatePosition(seg[pos * 2], seg[pos * 2 + 1]);
}

define Answer(long long l, long long r, long long pos, long long leftseg, long long rightseg) {
define def, ret_left, ret_right;
def.all = -1e14;
def.prefix = -1e14;
def.suffix = -1e14;
def.middle = -1e14;
if(l > rightseg || r < leftseg) {
return def;
}
if(l >= leftseg && r <= rightseg) {
return seg[pos];
}
long long mid = (l + r) / 2;
ret_left = Answer(l, mid, pos * 2, leftseg, rightseg);
ret_right = Answer(mid + 1, r, pos * 2 + 1, leftseg, rightseg);
def = UpdatePosition(ret_left, ret_right);
return def;
}

int main() {
long long n, m;
cin >> n;
for(long long i = 1; i <= n; i++) {
cin >> a[i];
}
for(long long i = 0; i < 2 * N; i++) {
seg[i].prefix = 0;
seg[i].suffix = 0;
seg[i].all = 0;
seg[i].middle = 0;
}
long long no_use = 1;
Construct(no_use, n, no_use);
cin >> m;
for(long long i = 1; i <= m; i++) {
long long l, r;
cin >> l >> r;
define def;
def = Answer(no_use, n, no_use, l, r);
cout << max(def.prefix, max(def.middle, max(def.suffix, def.all))) << endl;
}
return 0;
}
``````

Life would have been so difficult if seniors were not there. Thanks @may55