Untitled

 avatar
unknown
c_cpp
3 years ago
2.5 kB
7
Indexable
#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();
    }
}
Editor is loading...