Untitled
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...