Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef pair<int,int> pii;
- int bs(vector<pii> &arr,int data,int l,int r){
- int m = (l+r)/2;
- int x = arr[m].first;
- if(x == data){
- return arr[m].second;
- }
- if(l >= r){
- return -1;
- }else if(x < data){ // search in right
- return bs(arr,data,m+1,r);
- }else{ // search in left
- return bs(arr,data,l,m);
- }
- }
- int main(){
- int n,m;
- priority_queue<pii,vector<pii>,greater<pii>> pq;
- scanf("%d",&n);
- for(int i=1;i<=n;++i){
- int a;
- scanf("%d",&a);
- pq.push({a,i});
- }
- int r = 0;
- vector<pii> arr(n+1,{0,0});
- while(!pq.empty()){
- int a = pq.top().first;
- int b = pq.top().second;
- pq.pop();
- if(r != 0 && arr[r-1].first == a){
- arr[r-1].second = min(arr[r-1].second , b);
- }else{
- arr[r].first = a;
- arr[r].second = b;
- r++;
- }
- }
- scanf("%d",&m);
- for(int i=0;i<m;++i){
- int a;
- scanf("%d",&a);
- int poss = bs(arr,a,0,r-1);
- if(poss == -1){
- printf("Not found\n");
- }else{
- printf("%d\n",poss);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement