Submission #56017442

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 10;
const int P = 998244353;
int n, q;
int a[maxn];
int calc(int x, int d) {
    return upper_bound(a + 1, a + n + 1, x + d) - upper_bound(a + 1, a + n + 1, x - d - 1);
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    while (q--) {
        int b, k; cin >> b >> k;
        int l = 0, r = 2e8, mid, ans;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (calc(b, mid) >= k) ans = mid, r = mid - 1;
            else l = mid + 1;
        }
        cout << ans << '\n';
    }
    return 0;
}

Submission Info

Submission Time
Task D - K-th Nearest
User Rainer
Language C++ 17 (gcc 12.2)
Score 425
Code Size 742 Byte
Status AC
Exec Time 336 ms
Memory 3924 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 425 / 425
Status
AC × 3
AC × 21
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 02_minmax_00.txt, 02_minmax_01.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 1 ms 3464 KiB
00_sample_01.txt AC 1 ms 3532 KiB
00_sample_02.txt AC 1 ms 3444 KiB
01_random_00.txt AC 76 ms 3564 KiB
01_random_01.txt AC 288 ms 3804 KiB
01_random_02.txt AC 169 ms 3436 KiB
01_random_03.txt AC 290 ms 3924 KiB
01_random_04.txt AC 213 ms 3640 KiB
01_random_05.txt AC 289 ms 3856 KiB
01_random_06.txt AC 35 ms 3640 KiB
01_random_07.txt AC 288 ms 3728 KiB
01_random_08.txt AC 208 ms 3808 KiB
01_random_09.txt AC 289 ms 3864 KiB
01_random_10.txt AC 39 ms 3720 KiB
01_random_11.txt AC 289 ms 3816 KiB
01_random_12.txt AC 293 ms 3676 KiB
01_random_13.txt AC 336 ms 3860 KiB
01_random_14.txt AC 113 ms 3588 KiB
01_random_15.txt AC 166 ms 3852 KiB
02_minmax_00.txt AC 1 ms 3468 KiB
02_minmax_01.txt AC 117 ms 3868 KiB