MAXBTY - Editorial

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)

@tmwilliamlin

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;

}

Can you help me? Whats wrong with this?

Solution : https://www.codechef.com/viewsolution/30716889

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

@tmwilliamlin
Can some one please reply?

Read my this post .
unofficial short editorial

1 Like

@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?

@anon31329220 thanks bhai

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.