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???
Hi @tmwilliamlin , I am trying to understand your code . The solution being concise makes it harder for me to understand your code as I am beginner. I already learnt basics of segment tree. But understanding it completely and implementing it is a different ball game.Could you add some one line comments near variables and functions, describing their purpose, inside the solution you posted ? It will also help others.
Can someone please help with my code for this problem, thanks in advance:
https://www.codechef.com/viewsolution/32120279
@krikti Can you tell me what’s wrong in my code?
I had implemented exactly what is told in the editorial.
I tried many corner cases even tried to implement a random test case generators still no difference is found.
Link to my solution
I am trying to solve this question MAXBTY using following method:
Keep three segment trees: max prefix subarray sum, max suffix subarray sum and total sum.
For given query Q x y, answer is: total sum in range (x,y) + max prefix subarray sum in range (1, x-1) + max suffix subarray sum in range (y+1, N).
Can you please help in finding out why am I getting WA with this approach?
https://www.codechef.com/viewsolution/33135225
Got it. I was not updating array b on update operation.
is there a way to dec. the time taken by my solution…please tell
[code](is there a way to dec. the time taken by my solution…please tell CodeChef: Practical coding for everyone)
Yes, you can read the editorial.