# 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