結果

問題 No.3072 Speedrun Query
コンテスト
ユーザー nikoro256
提出日時 2025-03-21 22:32:58
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 397 ms / 2,500 ms
コード長 1,626 bytes
コンパイル時間 1,255 ms
コンパイル使用メモリ 115,512 KB
実行使用メモリ 7,936 KB
最終ジャッジ日時 2025-03-21 22:33:08
合計ジャッジ時間 7,586 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:27:20: warning: integer constant is too large for its type
   27 |     const ll inf = 100000000000000000000LL / 1000; // 10^20 (adjusted for LL)
      |                    ^~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>
using namespace std;
using ll = long long;

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

    int N, Ka, Kb;
    cin >> N >> Ka >> Kb;
    
    vector<ll> A(Ka), B(Kb);
    for (int i = 0; i < Ka; i++){
        cin >> A[i];
    }
    for (int i = 0; i < Kb; i++){
        cin >> B[i];
    }
    
    int Q;
    cin >> Q;
    
    const ll inf = 100000000000000000000LL / 1000; // 10^20 (adjusted for LL)
    ll a2b = inf;
    
    // AとB間の最小差分を計算
    for (auto a : A) {
        auto it = lower_bound(B.begin(), B.end(), a);
        if (it != B.end()){
            a2b = min(a2b, *it - a);
        }
        if (it != B.begin()){
            it--;
            a2b = min(a2b, a - *it);
        }
    }
    
    // 二分探索で与えた値に最も近い値との距離を返す関数
    auto dist = [&](const vector<ll>& arr, ll a) -> ll {
        ll res = inf;
        auto it = lower_bound(arr.begin(), arr.end(), a);
        if (it != arr.end()){
            res = min(res, *it - a);
        }
        if (it != arr.begin()){
            it--;
            res = min(res, a - *it);
        }
        return res;
    };
    
    // 各クエリに対する計算
    while (Q--) {
        ll s, t;
        cin >> s >> t;
        ll s2a = dist(A, s);
        ll s2b = dist(B, s);
        ll t2a = dist(A, t);
        ll t2b = dist(B, t);
        ll ans = min({ abs(t - s), s2a + t2a, s2b + t2b, s2a + a2b + t2b, s2b + a2b + t2a });
        cout << ans << "\n";
    }
    
    return 0;
}
0