i tried that way,my query working fine but update is not,shall we discuss more on BIT for this problem?
I tried the logic of editorās solution and implemented it in Python. Can anybody tell me why am I getting TLE for my solution.
Link to my solution
//Can anyone tell me what is wrong in this solution?
def make_list(A,N,L,R):
s=0
r=0
L.append(A[0])
R.append(A[N-1])
for i in range(1,N):
if L[i-1]>0:
L.append(A[i]+L[i-1])
else:
L.append(A[i])
if R[0]>0:
R.insert(0,A[N-1-i]+R[0])
else:
R.insert(0,A[N-1-i])
T=int(input())
for t in range(T):
L=[]
R=[]
N,Q=map(int,input().split())
A=[int(x) for x in input().split()]
make_list(A,N,L,R)
for q in range(Q):
v,x,y=input().split()
if v==āQā:
x,y=int(x),int(y)
s=0
for i in range(x,y-1):
s=s+A[i]
s=s+L[x-1]+R[y-1]
print(s)
elif v==āUā:
x,y=int(x),int(y)
A[x-1]=y
L=[]
R=[]
make_list(A,N,L,R)
there is very small and easy implementation
https://www.codechef.com/viewsolution/30709921
could somebody help me !!! i am getting wrong ans.
You are not updating the tree according to its lazy values when you perform querymin().
In Setterās Solution,
in queryMin function why is it that we have to return 0, if the STnodeās range is not inside the query interval of (i,j) ?
if we return 0 , then wouldnāt the returned zero affect the further actual querying ?
That is, if size of array is 5 and we call queryMin for (4,5) intervalā¦ the queryMin call for (1,3) returns 0 and if the minimum value returned by queryMin for (4,5) interval is +ve ; then the final answer will be given as 0 as the minimum value.
I checked that this code returns 0 instead of the actual positive value which was supposed to come.
So, shouldnāt the value returned for out of range condition be changed to infinity?
But thatās what i did(exactly same as that of setterās solution except for what i return) , getting some wrong answer for the sample test cases itself.
correct me if Iām wrong.
Is my basic logic is wrong?
if not i am getting wrong answer.
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n, q, x, y;
cin >> n >> q;
char query;
int arr[n];
for (int i = 0; i < n; ++i)
cin >> arr[i];
while (q--)
{
cin >> query >> x >> y;
int xIndex = x - 1;
int yIndex = y - 1;
if (query == 'Q') {
int tmpsum = 0, lmax = 0, rmax = 0, sum = 0;
//left side max sum
for (int i = xIndex -1; i >= 0; i--)
{
if (lmax < tmpsum + arr[i])
{
lmax = tmpsum + arr[i];
}
tmpsum += arr[i];
}
tmpsum = 0;
//right side max sum
for (int i = yIndex + 1; i < n; i++)
{
if (rmax < tmpsum + arr[i])
{
rmax = tmpsum + arr[i];
}
tmpsum += arr[i];
}
//sum between x and y
for (int i = xIndex; i <= yIndex; ++i)
{
sum += arr[i];
}
//max sum
sum += rmax + lmax;
cout << sum << "\n";
} else {
arr[xIndex] = y;
}
}
}
return 0;
}
What is negative prefix sum?
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.