AcWing 789. 数的范围
原题链接
简单
作者:
bruce
,
2021-01-22 13:35:44
,
所有人可见
,
阅读 201
#include<iostream>
#include<vector>
using namespace std;
const int N = 100010;
int a[N], n, m;
int firstK(int x)
{
int l = 0, r = n-1;
while(l < r)
{
int mid = (l + r) >>1;
if(a[mid] >= x)
{
r= mid;
}
else l = mid+1;
}
return l;
}
int lastK(int x)
{
int l = 0, r = n-1;
while(l < r)
{
int mid = (l + r + 1)>>1;
if(a[mid] <= x) l = mid;
else r = mid-1;
}
return l;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++) cin>>a[i];
while(m--)
{
int x ;
cin>>x;
int b = firstK(x);
int e = lastK(x);
if(a[b] != x) cout<<"-1 -1"<<endl;
else cout<<b<<" "<<e<<endl;
}
}