# Untitled

unknown
c_cpp
2 years ago
2.5 kB
3
Indexable
Never
```#include <bits/stdc++.h>
using namespace std;
int rightsearch(int arr[], int n, int lo, int hi, int val){
int mid, res;
while(lo<=hi){
mid=(lo+hi)/2;
if(val==arr[mid]){
return mid;
}
if(val<arr[mid]){
lo=mid+1; //hi=mid-1;
}
else
hi=mid-1; //lo=mid+1;
}
return -1;
}
int leftsearch(int arr[], int n, int lo, int hi, int val){
int mid, res;
while(lo<=hi){
mid=(lo+hi)/2;
if(val==arr[mid]){          //if(val=arr[mid]){
return mid;
}
if(val>arr[mid]){
lo=mid+1;  //hi=mid-1;
}
else{
hi=mid-1;  //lo=mid-1; ulta likhe the pehli baat ek jagah -1 hoga aur ek jagah +1
// phir koi value leke socho na...like ye leftsearch matlab chote se bda ho rha hoga array
// toh if wala val let say 10 ye > hai mid wale matlab kuch 6 lelo abb socho
// increasing array hai hamko chaiye 10 par mila 6, means upper jaana hoga, toh lo=mid+1
// koi bhi ek taraf ka sochlo bas dushra wala just opposite
}
}
return -1;
}
void solve(){
int n,q;
cin>>n>>q;
int arr[n];
for(int i=0; i<n; i++){
cin>>arr[i];
}
int k[q];
for(int i=0; i<q; i++){
cin>>k[i];
}
int lo, hi, mid, ans;//ans-bitoni point, i.e.  element with maximum value
lo=0; hi=n-1; ans=0;
while(lo<=hi){
mid=(lo+hi)/2;
if(arr[mid]<arr[mid+1]){
ans=mid;
lo=mid+1;
}
else{
hi=mid-1;
}
}
ans++;  //kyuki mid wala chota hoga na toh topmost mid+1 hoga na ishiliye ans++
cout<<ans<<'\n'; // isko comment kardena submit ke time
for(int i=0; i<q; i++){
if(k[i]==arr[ans])  //arr[ans] hoga k[ans] ki jagah, galti se likh diye hoge
cout<<ans+1<<'\n';
else{
if(leftsearch(arr, n, 0, ans-1, k[i])==-1)
cout<<rightsearch(arr, n, ans+1, n-1, k[i])+1<<'\n';
else if(rightsearch(arr, n, ans+1, n-1, k[i])==-1)
cout<<leftsearch(arr, n, 0, ans-1, k[i])+1<<'\n';
else
cout<<leftsearch(arr, n, 0, ans-1, k[i])+1<<" "<<rightsearch(arr, n, ans+1, n-1, k[i])+1<<'\n';
}
}
//cout<<ans<<'\n';
}
int main(){
ios_base::sync_with_stdio();
cin.tie(0); cout.tie(0);
int t;
cin>>t;
while(t--){
solve();
}
}```