結果

問題 No.3072 Speedrun Query
ユーザー AngrySadEight
提出日時 2025-03-13 00:29:47
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 341 ms / 2,500 ms
コード長 1,614 bytes
コンパイル時間 790 ms
コンパイル使用メモリ 76,632 KB
実行使用メモリ 7,936 KB
最終ジャッジ日時 2025-03-13 00:29:55
合計ジャッジ時間 7,280 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int INF = 1000000001;

int nearest(int x, vector<int> &vec) {
    auto itr = lower_bound(vec.begin(), vec.end(), x);
    int idx = itr - vec.begin();
    int ret = vec[idx] - x;
    idx--;
    ret = min(ret, x - vec[idx]);
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, KA, KB;
    cin >> N >> KA >> KB;
    vector<int> a(KA + 2);
    vector<int> b(KB + 2);
    a[0] = -INF;
    b[0] = -INF;
    for (int i = 0; i < KA; i++) {
        cin >> a[i + 1];
    }
    for (int i = 0; i < KB; i++) {
        cin >> b[i + 1];
    }
    a[KA + 1] = INF;
    b[KB + 1] = INF;
    int Q;
    cin >> Q;
    vector<int> s(Q);
    vector<int> t(Q);
    for (int i = 0; i < Q; i++) {
        cin >> s[i] >> t[i];
    }
    int dis_ab = N;
    for (int i = 1; i <= KA; i++) {
        dis_ab = min(dis_ab, nearest(a[i], b));
    }

    for (int i = 0; i < Q; i++) {
        int ans = N;

        // 直接向かう方法
        ans = min(ans, t[i] - s[i]);
        // ワープゾーン A のみ用いる方法
        ans = min(ans, nearest(s[i], a) + nearest(t[i], a));
        // ワープゾーン B のみ用いる方法
        ans = min(ans, nearest(s[i], b) + nearest(t[i], b));
        // ワープゾーン A -> B の順に用いる方法
        ans = min(ans, nearest(s[i], a) + dis_ab + nearest(t[i], b));
        // ワープゾーン B -> A の順に用いる方法
        ans = min(ans, nearest(s[i], b) + dis_ab + nearest(t[i], a));
        cout << ans << "\n";
    }
}
0