結果
問題 |
No.3072 Speedrun Query
|
ユーザー |
|
提出日時 | 2025-03-21 22:06:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 147 ms / 2,500 ms |
コード長 | 1,151 bytes |
コンパイル時間 | 2,098 ms |
コンパイル使用メモリ | 194,628 KB |
実行使用メモリ | 5,888 KB |
最終ジャッジ日時 | 2025-03-21 22:06:27 |
合計ジャッジ時間 | 6,557 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, ka, kb; cin >> n >> ka >> kb; vector<int> dp1(n, 1 << 30), dp2(n, 1 << 30); for(int i = 0; i < ka; i++){ int v; cin >> v; v--; dp1[v] = 0; } for(int i = 0; i < kb; i++){ int v; cin >> v; v--; dp2[v] = 0; } for(int i = 0; i + 1 < n; i++){ dp1[i + 1] = min(dp1[i + 1], dp1[i] + 1); dp2[i + 1] = min(dp2[i + 1], dp2[i] + 1); } for(int i = n - 2; i >= 0; i--){ dp1[i] = min(dp1[i], dp1[i + 1] + 1); dp2[i] = min(dp2[i], dp2[i + 1] + 1); } int mn = 1 << 30; for(int i = 0; i < n; i++){ mn = min(mn, dp1[i] + dp2[i]); } int q; cin >> q; while(q--){ int s, t; cin >> s >> t; s--, t--; int ans = abs(t - s); ans = min(ans, dp1[s] + dp1[t]); ans = min(ans, dp2[s] + dp2[t]); ans = min(ans, dp1[s] + dp2[t] + mn); ans = min(ans, dp2[s] + dp1[t] + mn); cout << ans << '\n'; } }