結果
問題 |
No.2897 2集合間距離
|
ユーザー |
![]() |
提出日時 | 2024-09-25 11:24:28 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 110 ms / 3,500 ms |
コード長 | 1,176 bytes |
コンパイル時間 | 4,745 ms |
コンパイル使用メモリ | 273,812 KB |
実行使用メモリ | 20,864 KB |
最終ジャッジ日時 | 2024-09-25 11:24:39 |
合計ジャッジ時間 | 7,646 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
#include <bits/stdc++.h> using namespace std; using i64 = long long; const int N = 2e5 + 10, M = 2e3 + 10; int n, x[N], y[N]; int g[M][M]; int ask(int x1, int y1, int x2, int y2) { if(x1 < 0) x1 = 0; if(y1 < 0) y1 = 0; if(x2 >= M) x2 = M - 1; if(y2 >= M) y2 = M - 1; return g[x2][y2] - g[x2][y1] - g[x1][y2] + g[x1][y1]; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for(int i = 1, a, b; i <= n; i ++) { cin >> a >> b; x[i] = a + b + 1; y[i] = a - b + 1001; } int m; cin >> m; for(int i = 1, a, b, x, y; i <= m; i ++) { cin >> a >> b; x = a + b + 1; y = a - b + 1001; g[x][y] ++; } for(int i = 1; i < M; i ++) for(int j = 1; j < M; j ++) g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1]; int l = -1, r = M; while(l + 1 < r) { int mid = (l + r) / 2; bool found = false; for(int i = 1; i <= n && !found; i ++) if(ask(x[i] - mid - 1, y[i] - mid - 1, x[i] + mid, y[i] + mid)) found = true; if(found) r = mid; else l = mid; } cout << r; }