제출 #1271416

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271416		SpyrosAliv	새 집 (APIO18_new_home)	C++20	0 / 100	559 ms	1114112 KiB

new_home

#include <bits/stdc++.h>
using namespace std;
#define int long long

// the answer for a set of stores and some point x is the minimum integer m such that MEX([x - m...x + m]) = k + 1
// MEX(l..r) = min(MEX(1..r), MEX(l..n))

const int MX = 1e8+1;

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k, q; cin >> n >> k >> q;
    vector<vector<int>> vals(MX);
    vector<int> pref(MX), suff(MX);
    for (int i = 1; i <= n; i++) {
        int x, t, a, b; cin >> x >> t >> a >> b;
        vals[x].push_back(t);
    }
    int currMex = 0;
    vector<bool> ex(k+1, false);
    for (int i = 1; i < MX; i++) {
        for (auto v: vals[i]) ex[v] = true;
        while (ex[currMex]) currMex++;
        pref[i] = currMex;
    }
    fill(ex.begin(), ex.end(), false);
    currMex = 0;
    for (int i = MX-1; i >= 1; i--) {
        for (auto v: vals[i]) ex[v] = true;
        while (ex[currMex]) currMex++;
        suff[i] = currMex;
    }
    for (int i = 1; i <= q; i++) {
        int x, y; cin >> x >> y;
        int lo = 0, hi = MX;
        int ans = -1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            int ll = max(1LL, x - mid);
            int rr = min(MX, x + mid);
            int val = min(pref[rr], suff[ll]);
            if (val == k+1) {
                ans = mid;
                hi = mid-1;
            }
            else lo = mid+1;
        }
        cout << ans << "\n";
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20