AcWing 789. 数的范围
原题链接
简单
作者:
linkirk
,
2021-02-05 23:19:10
,
所有人可见
,
阅读 321
#include<iostream>
#include<algorithm>
#include<sstream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<iomanip>
using namespace std;
#define lowbit(x) (x & -x)
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
#define rep(i, a, b) for(int i=(a);i<(b);i++)
#define REP(i, a, b) for(int i=(a);i<=(b);i++)
#define REV(i, a, b) for(int i=(a);i>=(b);i--)
#define CLR(a, x) memset(a,x,sizeof a)
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const long long INFLL = 0x3f3f3f3f;
int n,q;
int arr[100010];
int main() {
scanf("%d %d",&n,&q);
rep(i,0,n){
scanf("%d",&arr[i]);
}
rep(i,0,q){
int x;
scanf("%d",&x);
int l = 0,r = n - 1;
while(l < r){
int m = l + r >> 1;
if (arr[m] >= x) r = m;//说明M在ans的右侧,需要缩小右侧的空间,留下左侧的空间
else l = m + 1;
}
if (arr[r] == x){
cout << r << ' ';
r = n - 1;
while (l < r){
int m = l + r + 1 >> 1; //向上取整,避免死循环
if (arr[m] <= x) l = m;
else r = m - 1;
}
cout << r << endl;
}else{
cout << "-1 -1" <<endl;
}
}
return 0;
}