MAXBTY - Editorial

@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 : https://www.youtube.com/watch?v=wYfp3ViLC-s&t=20s

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

@jprm2 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.

Capture

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.
[https://www.codechef.com/viewsolution/30791349]–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???

Can someone check my solution? It’s in Python.

https://www.codechef.com/viewsolution/30844913

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.

https://www.codechef.com/viewsolution/30688655
How about this?