Getting WA for using Binary Search on L,R in BURARRAY

I used set + binary search on [L,R] for each query and got TLE and WA , any suggestions ?

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector< int >
#define pb push_back
#define MP make_pair
#define fi first
#define se second
unordered_set < int > s1;
int fun(int l,int r)
{
if(l<=r)
{
int m=l+(r-l)/2;
if(s1.find(m)==s1.end())
return max(m,fun(m+1,r));
if(l!=r)
return max(fun(m+1,r),max(l,m-1));
}
return -1LL;
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cerr.tie(0);
int T;
cin>>T;
while(T–)
{
int n,i,t,x,y,p,Q,l,r,s=0,ans,mid,q;
cin>>n>>Q;
s=0;
ans=0;
s1.clear();
while(Q–)
{
cin>>t;
if(t==1)
{
cin>>y;
x=y+s;
s1.insert(x);
}
else
{
cin>>p>>q;
l=p+s;
r=q+s;
ans=fun(l,r);
if(ans>0&&(s1.find(ans)==s1.end()))
{
cout<<ans<<endl;
s=(s%n+ans%n)%n;
}
else
cout<<“0”<<endl;
}
}
}

}

mujtaba1747,

The problem might be that initially when A[i]=i+1 (0-indexed arrays), the array is sorted, but when you apply the first query some consider some random elements in the array getting initialized to 0. So the newly formed array is no longer sorted. This might be a case with using binary search. :grin:

1 Like