When each element of prefix sum array is multiplied by -1, we get the negative prefix sum array
Instead of maintaining 2 segment trees, i maintained values of segment sum (z), maximum prefix (y) and maximum suffix sum (x) at each node in the segment tree, then output max(z,x+z,y+z,x+y+z) . But I am getting a WA. Is my logic incorrect? Please help me find what’s wrong with my code: CodeChef: Practical coding for everyone
@jugshaurya william lin has explained the mysara solution on his youtube channel.
Link : MYSARA Solution - CodeChef March Cook-Off 2020 - YouTube
#include<bits/stdc++.h>
#define maxn 100001
#define maxt 500005
using namespace std;
struct node
{
long long x;
long long n;
};
struct node tree[maxt];
long long max(long long a,long long b)
{
if(a>b) return a;
else return b;
}
long long min(long long a,long long b)
{
if(a>b) return b;
else return a;
}
node build(long long pre[],int v,int l,int r)
{
if(l==r)
{
tree[v].x=pre[l];
tree[v].n=pre[l];
return tree[v];
}
else
{
node m1,m2;
int mid = (l+r)/2;
m1 = build(pre,2*v,l,mid);
m2 = build(pre,2*v+1,mid+1,r);
tree[v].x=max(m1.x,m2.x);
tree[v].n=min(m1.n,m2.n);
return tree[v];
}
}
long long Qx(int v,int l,int r,int x,int y)
{
if(l==x&&r==y)
{
return tree[v].x;
}
int mid = (l+r)/2;
if(y<=mid)
{
return Qx(2*v,l,mid,x,y);
}
if(x>mid)
{
return Qx(2*v+1,mid+1,r,x,y);
}
return max(Qx(2*v,l,mid,x,mid),Qx(2*v+1,mid+1,r,mid+1,y));
}
long long Qn(int v,int l,int r,int x,int y)
{
if(l==x&&r==y)
{
return tree[v].n;
}
int mid = (l+r)/2;
if(y<=mid)
{
return Qn(2*v,l,mid,x,y);
}
if(x>mid)
{
return Qn(2*v+1,mid+1,r,x,y);
}
return min(Qn(2*v,l,mid,x,mid),Qn(2*v+1,mid+1,r,mid+1,y));
}
node ux(int v,int l,int r,int x,long long add,long long pre[])
{
int mid=(l+r)/2;
if(l==r&&l>=x)
{
pre[l]+=add;
tree[v].x=pre[l];
tree[v].n=pre[l];
return tree[v];
}
if(x>=mid+1)
{
node m1=tree[2*v];
node m2=ux(2*v+1,mid+1,r,x,add,pre);
tree[v].x = max(m1.x,m2.x);
tree[v].n = max(m1.n,m2.n);
return tree[v];
}
node m1,m2;
m1=ux(2*v,l,mid,x,add,pre);
m2=ux(2*v+1,mid+1,r,x,add,pre);
tree[v].x = max(m1.x,m2.x);
tree[v].n = max(m1.n,m2.n);
return tree[v];
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n,q;
cin>>n;
cin>>q;
long long b[n+1]={0};
long long pre[n+1]={0};
for(int i=1;i<=n;++i)
{
cin>>b[i];
pre[i]=b[i]+pre[i-1];
}
build(pre,1,1,n);
while(q--)
{
char w;
cin>>w;
if(w=='Q')
{
int x,y;
cin>>x>>y;
long long a,b;
a=Qx(1,1,n,y,n);
b=Qn(1,1,n,1,x-1);
if(b>0) b=0;
cout<<a-b<<endl;
}
else
{
int x;
long long y;
cin>>x;
cin>>y;
long long add;
add=y-b[x];
ux(1,1,n,x,add,pre);
}
}
}
return 0;
}
I have used segmented tree then also it is showing time limit exceeded. Please help, how can I optimize it further?
Please tell me what is wrong in my code:
https://www.codechef.com/viewsolution/30761682
My Code is almost similar to setters code,thats why am asking
Please help guys
@tmwilliamlin @imanik @ezio_26 @everule1
Can , someone please explain the example input in the question ?
5 5
-1 2 -2 1 -3
How in the first query - Q 3 5 , the output is -2
and in the fifth query - Q 3 5 the output is -1 ?
That helped. Thanks!
I guess no, cause segment tree does updates and queries both in logN time while update in dp will take O(N) time.
in worst case chef can chose l=1(which is <x) and sum will be starting from index 1 and Hence value of queryMin has maximum possible value of 0.
here is the case
49 52 48 51 40 -100 50
for Q 3 5 ans=49+52+48+51+40
Thank you bro.
shit!! I didn’t see this obvious edge case.
1 Like
ok thank you
Can somebody tell me why my code is giving WA? I believe updIndex() is the culprit here.
Link to the code.
Can someone help me. Why am I getting segmentation fault in this code?
#include<bits/stdc++.h>
#define maxn 100001
#define maxt 400005
using namespace std;
struct node
{
long long x;
long long n;
};
struct node tree[maxt] = {0};
long long lazy[maxt] = {0};
long long max(long long a,long long b)
{
if(a>b) return a;
else return b;
}
long long min(long long a,long long b)
{
if(a>b) return b;
else return a;
}
node build(long long pre[],int v,int l,int r)
{
lazy[v]=0;
if(l==r)
{
tree[v].x=pre[l];
tree[v].n=pre[l];
lazy[2*v]=0;
lazy[2*v+1]=0;
return tree[v];
}
else
{
node m1,m2;
int mid = (l+r)/2;
m1 = build(pre,2*v,l,mid);
m2 = build(pre,2*v+1,mid+1,r);
tree[v].x=max(m1.x,m2.x);
tree[v].n=min(m1.n,m2.n);
return tree[v];
}
}
void lazyp(int v,long long i)
{
lazy[v]+=i;
tree[v].x+=lazy[v];
tree[v].n+=lazy[v];
lazy[2*v]+=lazy[v];
lazy[2*v+1]+=lazy[v];
lazy[v]=0;
}
long long Qx(int v,int l,int r,int x,int y)
{
lazyp(v,0);
if(l>=x&&r<=y)
{
return tree[v].x;
}
int mid = (l+r)/2;
if(y<=mid)
{
return Qx(2*v,l,mid,x,y);
}
if(x>mid)
{
return Qx(2*v+1,mid+1,r,x,y);
}
return max(Qx(2*v,l,mid,x,y),Qx(2*v+1,mid+1,r,x,y));
}
long long Qn(int v,int l,int r,int x,int y)
{
lazyp(v,0);
if(l>=x&&r<=y)
{
return tree[v].n;
}
int mid = (l+r)/2;
if(y<=mid)
{
return Qn(2*v,l,mid,x,y);
}
if(x>mid)
{
return Qn(2*v+1,mid+1,r,x,y);
}
return min(Qn(2*v,l,mid,x,y),Qn(2*v+1,mid+1,r,x,y));
}
node ux(int v,int l,int r,int x,long long add,long long pre[])
{
if(l==r&&l>=x)
{
lazyp(v,add);
pre[l]=tree[v].x;
return tree[v];
}
int mid=(l+r)/2;
if(x>=mid+1)
{
lazyp(2*v,0);
node m1=tree[2*v];
node m2=ux(2*v+1,mid+1,r,x,add,pre);
tree[v].x = max(m1.x,m2.x);
tree[v].n = min(m1.n,m2.n);
return tree[v];
}
node m1,m2;
lazyp(2*v+1,add);
m1=ux(2*v,l,mid,x,add,pre);
m2=tree[2*v+1];
tree[v].x = max(m1.x,m2.x);
tree[v].n = min(m1.n,m2.n);
return tree[v];
}
int main()
{
int t;
cin>>t;
int n,q;
long long b[maxn]={0};
long long pre[maxn]={0};
char w;
while(t--)
{
cin>>n;
cin>>q;
for(int i=1;i<=n;++i)
{
cin>>b[i];
pre[i]=b[i]+pre[i-1];
}
build(pre,1,1,n);
while(q--)
{
cin>>w;
if(w=='Q')
{
int x,y;
cin>>x>>y;
long long a,b;
a=Qx(1,1,n,y,n);
b=Qn(1,1,n,1,x-1);
if(b>0) b=0;
cout<<a-b<<endl;
}
else
{
int x;
long long y;
cin>>x;
cin>>y;
long long add;
add=y-b[x];
ux(1,1,n,x,add,pre);
b[x]=y;
}
}
}
return 0;
}has anyone done this using fenwick tree, please share your solution.
thank you
I tried to do it without segtrees.First i calculated max sum from l till x,then max sum from y till r and then add them with sum of beauties between x and y…simple logic and code is easy to understand.I am getting correct answer for given test case but incorrect answer when i submitted the code.Implementation is O(n) so i think there is no problem of time complexity.
[CodeChef: Practical coding for everyone]–my code
Since we have to maximize Cr-Cl-1,. Cr must be the maximum and r >=y , Cr is the maximum prefix sum from 1 to r. Now Cl-1 must minimum in the range 1 to l-1, and the result obtained is the maximum possible.
Now I am not understanding why two segment trees are used and why suffix is needed as prefix alone can calculate the answer, why things are made so complicated???