結果
問題 | No.3072 Speedrun Query |
ユーザー |
![]() |
提出日時 | 2025-03-21 23:17:03 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 177 ms / 2,500 ms |
コード長 | 1,668 bytes |
コンパイル時間 | 6,866 ms |
コンパイル使用メモリ | 333,192 KB |
実行使用メモリ | 10,284 KB |
最終ジャッジ日時 | 2025-03-21 23:17:18 |
合計ジャッジ時間 | 10,321 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 |
ソースコード
#include <atcoder/all> #include <bits/stdc++.h> #define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++) using namespace atcoder; using namespace std; typedef long long ll; template <typename T> ostream &operator<<(ostream &os, const vector<T> &v) { int n = v.size(); rep(i, 0, n) { os << v[i] << " \n"[i == n - 1]; } return os; } vector<int> f(vector<int> a, int n) { vector<int> dist(n, 5e5); for (int u : a) dist[u] = 0; queue<int> q; for (int u : a) q.push(u); while (!q.empty()) { int u = q.front(); q.pop(); for (int v : {u - 1, u + 1}) { if (0 <= v && v < n && dist[v] == 5e5) { dist[v] = dist[u] + 1; q.push(v); } } } return dist; } int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); int n, ka, kb; cin >> n >> ka >> kb; vector<int> a(ka), b(kb); rep(i, 0, ka) cin >> a[i], a[i]--; rep(i, 0, kb) cin >> b[i], b[i]--; auto dista = f(a, n); auto distb = f(b, n); int abmn = 5e5; rep(i, 0, ka) { int j = lower_bound(b.begin(), b.end(), a[i]) - b.begin(); int l = max(0, j - 2), r = min(kb - 1, j + 3); rep(k, l, r + 1) { abmn = min(abmn, abs(a[i] - b[k])); } } int q; cin >> q; while (q--) { int l, r; cin >> l >> r; l--, r--; int ans = abs(l - r); ans = min(ans, dista[l] + dista[r]); ans = min(ans, distb[l] + distb[r]); ans = min(ans, dista[l] + distb[r] + abmn); ans = min(ans, distb[l] + dista[r] + abmn); cout << ans << '\n'; } }