https://www.codechef.com/viewsolution/30687934
Can anyone help me with it?
My logic is same as tester’s soltution the only difference is 0based and 1 based index
https://www.codechef.com/viewsolution/30687418
Can someone tell me what is wrong with this solution?
I’m unable to figure it out.
can we do this question with help of binary indexed tree ( used in LAZER of March 2020 long challenge) instead of segment tree?
link of LAZER : https://www.codechef.com/MARCH20B/problems/LAZER
Definitely you can if you preserve prefix suffix and sum in a range as per above shared article by me.
In-fact The second question of div1 of previous cook off can also be done the same way. This cook offs and previous cook offs second question were almost similar quickly check both the questions.
1 Like
LIne 106 :-node y1=query(1,0,n-1,0,l-2);
Querying range 1 to x-1 and getting a node.
Line 107: - node y2=query(1,0,n-1,r,n-1);
Querying range y+1 to n and getting a node
in each node y , y1 and y2 we have maximum prefix subarray sum , maximum suffix subarray sum , total sum of subarray
thus now we got all the things for all the three ranges that is 1 to x-1 x to y and y+1 to n
now
x=maximum suffix subarray sum in range 1 to x-1 obtain this from node y1
and y=maximum prefix subarray sum in range y+1 to n and obtain this from node y2
z=sum of subarray x to y and obtain this from node y
by using these three values
output max(z,x+z,y+z,x+y+z) as answer.
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