FREQUENT - Frequent values - SPOJ Solution C++ ~ CodingWithArt

➤ Problem Link : FREQUENT

👉 Hint : edit please

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;

#define ll long long int

ll st[800001];
ll arr[500001];
int leftp[500001],rightp[500001];
int cnt[800005];
int offset=100001;
void build(int v, ll l, ll r)
{
	if(l==r)
	{
		st[v]=cnt[l];
		return;
	}
	int mid=(l+r)/2;
	build(2*v,l,mid);
	build(2*v+1,mid+1,r);
	st[v]=max(st[2*v],st[2*v+1]);
}

int query(int v, int s, int e,int l, int r)
{
	if(s>r || e<l)
		return 0;
	if(s>=l && e<=r)
		return st[v];
	int mid=(s+e)/2;
	return max(query(2*v,s,mid,l,r),query(2*v+1,mid+1,e,l,r));
}

int main()
{
	while(1)
	{
		int n,q;
		cin>>n;
		if(n==0)
			break;
		cin>>q;
		memset(cnt,0,sizeof(cnt));
        ll mx=-1;
		for(int i=1;i<=n;i++)
		{
			cin>>arr[i];
			arr[i]+=offset;
			cnt[arr[i]]++;
			mx=max(mx,arr[i]);
		}
    
		leftp[1]=1;

		for(int i=2;i<=n;i++)
		{
			if(arr[i]==arr[i-1])
				leftp[i]=leftp[i-1];
			else
				leftp[i]=i;
		}
		rightp[n]=n;
		for(int i=n-1;i>=1;i--)
		{
			if(arr[i]==arr[i+1])
				rightp[i]=rightp[i+1];
			else
				rightp[i]=i;
		}
	
		build(1,1,mx);
		int a,b,ans;
		while(q--)
		{
			cin>>a>>b;
		
			if(arr[a]==arr[b])
			{
				cout<<b-a+1<<"\n";
				continue;
			}
			int p=rightp[a];
			int m=leftp[b];
			
			ans=max(p-a+1,b-m+1);
			
			ans=max(ans,query(1,1,mx,arr[p+1],arr[m-1]));
			cout<<ans<<"\n";
		}

	}
}

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.

😇Happy Learning!!

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.