結果

問題 No.3072 Speedrun Query
ユーザー srjywrdnprkt
提出日時 2025-03-21 22:12:32
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 336 ms / 2,500 ms
コード長 1,297 bytes
コンパイル時間 3,451 ms
コンパイル使用メモリ 276,460 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-21 22:12:42
合計ジャッジ時間 9,336 ms
ジャッジサーバーID
(参考情報)
judge7 / judge6
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <bits/stdc++.h>
//#include <atcoder/modint>

using namespace std;
//using namespace atcoder;
using ll = long long;
//using mint = modint998244353;

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int N, K1, K2, Q, mi=1e9;
    cin >> N >> K1 >> K2;
    vector<int> a(K1+2), b(K2+2);
    a[0] = -1e8;
    a[K1+1] = 1e8;
    b[0] = -1e8;
    b[K2+1] = 1e8;
    for (int i=1; i<=K1; i++) cin >> a[i];
    for (int i=1; i<=K2; i++) cin >> b[i];
    for (int i=1; i<=K1; i++){
        auto it = lower_bound(b.begin(), b.end(), a[i]);
        mi = min(*it-a[i], mi);
        it--;
        mi = min(mi, a[i]-*it);
    }

    cin >> Q;
    while(Q--){
        int s, t, ans, sa, sb, ta, tb;
        cin >> s >> t;
        ans = t-s;
        auto it = lower_bound(a.begin(), a.end(), s);
        sa = min(*it-s, s-*prev(it));
        it = lower_bound(b.begin(), b.end(), s);
        sb = min(*it-s, s-*prev(it));
        it = lower_bound(a.begin(), a.end(), t);
        ta = min(*it-t, t-*prev(it));
        it = lower_bound(b.begin(), b.end(), t);
        tb = min(*it-t, t-*prev(it));
        ans = min(ans, sa+ta);
        ans = min(ans, sb+tb);
        ans = min(ans, sa+tb+mi);
        ans = min(ans, sb+ta+mi);
        cout << ans << '\n';
    }

    return 0;
}
0