結果
問題 |
No.2897 2集合間距離
|
ユーザー |
![]() |
提出日時 | 2024-09-21 11:06:08 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 300 ms / 3,500 ms |
コード長 | 1,682 bytes |
コンパイル時間 | 4,003 ms |
コンパイル使用メモリ | 256,456 KB |
最終ジャッジ日時 | 2025-02-24 11:08:36 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; #define rep(i, n) for(int i=0;i<(n);++i) #define rep1(i, n) for(int i=1;i<=(n);i++) #define ll long long using mint = modint998244353; using P = pair<ll,ll>; using lb = long double; using T = tuple<ll, ll, ll>; #ifdef LOCAL # include <debug_print.hpp> # define dbg(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else # define dbg(...) (static_cast<void>(0)) #endif int op(int a, int b) { return a+b; } int e() { return 0; } int main() { int n; cin >> n; vector<pair<int,int>> xn, xm; const int base = 1e3; rep(i,n) { int X, Y; cin >> X >> Y; xn.emplace_back(X+Y, X-Y+base); } int m; cin >> m; rep(i,m) { int X, Y; cin >> X >> Y; xm.emplace_back(X+Y, X-Y+base); } sort(xn.begin(),xn.end()); sort(xm.begin(),xm.end()); int l = -1; int r = 1e7; while(r-l>1) { fenwick_tree<int> bit(2*base+5); int mid = (l+r)/2; int j = 0; int k = 0; bool ok = false; rep(i,n) { while(j<m && xm[j].first<=xn[i].first+mid) { bit.add(xm[j].second,1); j++; } while(k<m && xm[k].first<xn[i].first-mid) { bit.add(xm[k].second, -1); k++; } int val = bit.sum(max(0, xn[i].second-mid), min(2*base+5, xn[i].second+mid+1)); if(val>=1) { ok = true; break; } } if(ok) r = mid; else l = mid; } cout << r << endl; return 0; }