But the point is that I am not getting TLE. I am getting WA.
That’s strange. This is your code, right? H2wjUT - Online IDE & Debugging Tool - Ideone.com
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
XD@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
MAXimal :: algo :: Дерево отрезков 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?
Link: MVPSue - Online C++0x Compiler & Debugging Tool - Ideone.com
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,node2,start,mid);
build_tree(arr,tree,node2+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[node2+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,node2+1,mid+1,end,left,right);
if(mid>=right)
return ans(tree,node2,start,mid,left,right);
total t1=ans(tree,node2,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() {
// your code goes here
int n;
cin>>n;
ll arr[n];
total tree[4n];
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;
}