AcWing 789. 数的范围
原题链接
简单
作者:
评测机上抹点绿
,
2021-01-18 00:57:34
,
所有人可见
,
阅读 443
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<algorithm>
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
#define int ll
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define MOD 1e9 + 7
using namespace std;
int read()
{
int w = 1, s = 0;
char ch = getchar();
while (ch < '0' || ch>'9') { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { s = s * 10 + ch - '0';ch = getchar(); }
return s * w;
}
//最大公约数
int gcd(int x,int y) {
if(x<y) swap(x,y);//很多人会遗忘,大数在前小数在后
//递归终止条件千万不要漏了,辗转相除法
return x % y ? gcd(y, x % y) : y;
}
//计算x和y的最小公倍数
int lcm(int x,int y) {
return x * y / gcd(x, y);//使用公式
}
int ksm(int a, int b, int mod) { int s = 1; while(b) {if(b&1) s=s*a%mod;a=a*a%mod;b>>=1;}return s;}
//------------------------ 以上是我常用模板与刷题几乎无关 ------------------------//
const int N = 100010;
int a[N];
signed main()
{
int n = read(), m = read();
for (int i = 0 ;i < n; i++) a[i] = read();
while (m--) {
int x = read();
//模板1
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (a[mid] >= x) r = mid;
else l = mid + 1;
}
if (a[l] != x) printf("-1 -1\n");
else {
//这里二分完,l和r是一样的,输出什么都可以
printf("%lld ", l);
//模板2
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;
}
//这里二分完,l和r是一样的,输出什么都可以
printf("%lld\n", r);
}
}
return 0;
}