結果
問題 |
No.3072 Speedrun Query
|
ユーザー |
|
提出日時 | 2025-08-24 19:55:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 856 ms / 2,500 ms |
コード長 | 2,675 bytes |
コンパイル時間 | 2,209 ms |
コンパイル使用メモリ | 200,472 KB |
実行使用メモリ | 16,936 KB |
最終ジャッジ日時 | 2025-08-24 19:55:58 |
合計ジャッジ時間 | 17,442 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> Pii; typedef pair<int, ll> Pil; typedef pair<ll, ll> Pll; typedef pair<ll, int> Pli; typedef vector<vector<ll>> Mat; #define fi first #define se second const ll MOD = 1e9 + 7; const ll MOD2 = 998244353; const ll MOD3 = 1812447359; const ll INF = 1ll << 62; const double PI = 2 * asin(1); void yes() { printf("yes\n"); } void no() { printf("no\n"); } void Yes() { printf("Yes\n"); } void No() { printf("No\n"); } void YES() { printf("YES\n"); } void NO() { printf("NO\n"); } int n, ka, kb, a[int(3e5 + 5)], b[int(3e5 + 5)]; int q, s[int(3e5 + 5)], t[int(3e5 + 5)], ans[int(3e5 + 5)]; priority_queue<Pii, vector<Pii>, greater<Pii>> que_a, que_b; bool visited_a[int(3e5 + 5)], visited_b[int(3e5 + 5)]; int dist_a[int(3e5 + 5)], dist_b[int(3e5 + 5)], dist_ab; void prepare_dist() { while (!que_a.empty()) { Pii q = que_a.top(); que_a.pop(); if (visited_a[q.second]) { continue; } visited_a[q.second] = true; dist_a[q.second] = q.first; for (int i = -1; i <= 1; i++) { int next = q.second + i; if (1 <= next && next <= n && !visited_a[next]) { que_a.push({q.first + 1, next}); } } } while (!que_b.empty()) { Pii q = que_b.top(); que_b.pop(); if (visited_b[q.second]) { continue; } visited_b[q.second] = true; dist_b[q.second] = q.first; for (int i = -1; i <= 1; i++) { int next = q.second + i; if (1 <= next && next <= n && !visited_b[next]) { que_b.push({q.first + 1, next}); } } } dist_ab = 1e9; int now_b = 1; for (int i = 1; i <= ka; i++) { for (int j = now_b; j <= kb; j++) { if (a[i] >= b[j]) { now_b = j; } else { break; } } dist_ab = min(dist_ab, abs(a[i] - b[now_b])); dist_ab = min(dist_ab, abs(a[i] - b[max(now_b - 1, 1)])); dist_ab = min(dist_ab, abs(a[i] - b[min(now_b + 1, kb)])); } return; } int main() { cin >> n >> ka >> kb; for (int i = 1; i <= ka; i++) { cin >> a[i]; que_a.push({0, a[i]}); } for (int i = 1; i <= kb; i++) { cin >> b[i]; que_b.push({0, b[i]}); } prepare_dist(); cin >> q; for (int i = 1; i <= q; i++) { cin >> s[i] >> t[i]; ans[i] = abs(s[i] - t[i]); ans[i] = min(ans[i], dist_a[s[i]] + dist_a[t[i]]); ans[i] = min(ans[i], dist_a[s[i]] + dist_ab + dist_b[t[i]]); ans[i] = min(ans[i], dist_b[s[i]] + dist_b[t[i]]); ans[i] = min(ans[i], dist_b[s[i]] + dist_ab + dist_a[t[i]]); } for (int i = 1; i <= q; i++) { cout << ans[i] << endl; } return 0; }