結果
問題 | No.3072 Speedrun Query |
ユーザー |
![]() |
提出日時 | 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) | ^~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#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; }