I couldn’t think of any other approach other than bruteforce.
So I just want a hint on how to approach this problem.I have seen other’s accepted solutions but couldn’t understand anything.So I’ve come here for help.
1 Like
For each index precompute the index of next different number both to left and right of that index and then for any query l,r we can check that if a[l]==a[r] and next[l] =previous[r] then its yes else no. Think of edge cases and tell me if there is anything which is not clear.
CODE
#include<bits/stdc++.h>
using namespace std ;
void solve(){
int n,q ;cin >>n >> q ;
vector<int>a(n),nx(n),pr(n);
for(int &x:a)
cin >> x;
int ls =n-1 ;nx[ls]=-1 ;
for(int i=n-2;~i;--i){
if(a[i]^a[i+1])
nx[i]=i+1,ls=i ;
else
nx[i]=nx[ls] ;
}
ls=0,pr[ls]=-1 ;
for(int i=1;i<n;i++){
if(a[i-1]^a[i])
pr[i]=i-1,ls=i ;
else
pr[i]=pr[ls] ;
}
while(q--){
int l,r ;cin >> l >> r ;
--l;--r ;
if(a[l]==a[r])
cout << (nx[l]==pr[r]?"YES":"NO") << '\n';
else
cout << ((l==pr[r] || nx[l]==r)?"YES":"NO") <<'\n';
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t ;
cin >> t ;
while(t--)
solve() ;
}
PS: What’s up with this codechef discuss formatting lately someone please fix it.
Ill try. Thanks
1 Like
Can be also solved using binary search
nice bro i didn’t think thought of binary search thanks for this…
i solved it using pbds…