AtCoder Beginner Contest 205 D - Kth Excluded
June 14, 2021\(K_q\)ごとに二部探索で答えを直接検索しても通すことができる。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n, q;
cin >> n >> q;
vector<ll> a(n), k(q);
for(int i = 0; i < n; i++)
cin >> a[i];
for(int i = 0; i < q; i++)
cin >> k[i];
for(auto kk : k) {
ll lb = 0ll, ub = numeric_limits<ll>::max();
while(ub - lb > 1) {
ll mid = (ub + lb) / 2ll;
auto it = lower_bound(a.begin(), a.end(), mid);
ll index = it - a.begin();
if(kk < mid - index) {
ub = mid;
} else {
lb = mid;
}
}
cout << lb << endl;
}
return 0;
}