SNAKEEAT - Editorial

@tony_hager thanks a lot for this.

I used merge sort and binary search in my code, still I was getting Time Limit Exceeded error My code

@victor_arsenal, I have run your program against my test files and it gives exactly the same output as my own program, which got AC.

wow, strange. When I submitedt it in the contest, it returned WA. Anyway, thank you very much.

Thank you for your videos. I think it will be great if you do some hard problems or problems based on some rare topic :slight_smile: Keep up the good work!

Hi @ista2000,
Thanks for the feedback!
There are some hard and rare problems picked up on the channel: Mo’s Algorithm with Updates, Fourier Transform, Persistent Segment Trees etc…
You could have a look at them.

1 Like

can someone please help me with my code ?
getting WA. though I couldn’t find any test case

#include<bits/stdc++.h>
using namespace std;
#define ll long long int

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);	cout.tie(0);
int test;
cin>>test;
while(test--){
	ll i,q,j,k,n,m;
	cin>>n>>q;
	vector<ll> v(n+1,0),dif(n+1,0);
	for(i=1;i<=n;i++)
		cin>>v[i];
	sort(v.begin(), v.end());
	for(i=1;i<=n;i++)
		dif[i]=dif[i-1]+v[i];//prefix sum
	while(q--){	//use tree=snake
		cin>>k;
		ll low=0,high=n;
		while(low<high){//we ask if mid number of trees are possible
			ll mid=(low+high+1)/2;//throws back to high ,i.e. low=4,high=5 gives mid=5
			ll index=n-mid,big_index=lower_bound(v.begin(),v.end(),k)-v.begin();
			big_index-=(v[big_index]>k?1:0);//last index where v[i]<k
			ll val=k*(big_index-index)-(dif[big_index]-dif[index]);
			//val is number of tree required to make mid number of trees possible
			val=max(val,0LL);//not required now
			if((index>=val && big_index>index) || big_index<=index)
				low=mid;//if mid number of trees are possible
			else high=mid-1; 
		}
		cout<<high<<"\n";
	}
}
	return 0;
}