 # GDINT - Editorial

Deepavali Code Battle - Good Integers

Author: Om Bindal
Editorialist: Om Bindal

EASY

# PREREQUISITES:

Prefix-sum, Array

# EXPLANATION:

Let us call an integer good if it is different from either of A_1, A_2, \dots, A_N.

For each i, find the number of good integers less than or equal to A_i . and record them as C_i.

Then, the K-th smallest good integer can be found as follows:

• If C_N < K
• The answer is always greater than A_N. Since every integer greater than A_N is a good integer, the answer is A_N + (K - C_N)​.
• If C_N \geq K
• Find with binary search the minimum i such that C_i \geq K, then the answer is greater than A_{i - 1}.​ and less than A_i (where we assume A_0 = 0). Since every integer greater than A_{i−1}​ and less than A_i. is a good integer, the answer is (A_i - 1) - (C_i - K), that is, C_i - K elements before A_{i - 1}.

The complexity is O(N+QlogN).

# SOLUTIONS:

Setter's Solution
``````#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
int N, Q;
cin >> N >> Q;
vector<long long> A(N);
for (auto& x : A) {
cin >> x;
}
vector<long long> low(N);
for (int i = 0; i < N; ++i) {
low[i] = A[i] - (i + 1);
}
while (Q--) {
long long K;
cin >> K;
const int idx = lower_bound(low.begin(), low.end(), K) - low.begin();
if (idx == N) {
cout << A[N - 1] + (K - low[N - 1]) << '\n';
} else {
cout << A[idx] - (low[idx] - K + 1) << '\n';
}
}
return 0;
}
``````