結果
問題 | No.2897 2集合間距離 |
ユーザー | tottoripaper |
提出日時 | 2024-09-22 17:59:19 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,058 ms / 3,500 ms |
コード長 | 2,506 bytes |
コンパイル時間 | 2,514 ms |
コンパイル使用メモリ | 215,320 KB |
実行使用メモリ | 43,496 KB |
最終ジャッジ日時 | 2024-09-22 17:59:35 |
合計ジャッジ時間 | 15,128 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
#include <bits/stdc++.h> #define fst(t) std::get<0>(t) #define snd(t) std::get<1>(t) using ll = std::int64_t; using P = std::tuple<int, int>; int main(){ std::cin.tie(nullptr); std::ios::sync_with_stdio(false); int N; std::cin >> N; std::vector<P> p(N); for(int i=0;i<N;i++){ int x, y; std::cin >> x >> y; p[i] = std::make_tuple(x + y, x - y); } int M; std::cin >> M; std::vector<P> q(M); for(int i=0;i<M;i++){ int x, y; std::cin >> x >> y; q[i] = std::make_tuple(x + y, x - y); } std::sort(std::begin(q), std::end(q)); int numLeaves = 1; while(M > numLeaves){numLeaves *= 2;} std::vector<std::vector<int>> seg(numLeaves * 2); for(int i=0;i<M;i++){ seg[i + numLeaves].emplace_back(snd(q[i])); } for(int i=numLeaves-1;i>0;i--){ std::merge( std::begin(seg[i * 2]), std::end(seg[i * 2]), std::begin(seg[i * 2 + 1]), std::end(seg[i * 2 + 1]), std::back_inserter(seg[i]) ); } int res = 3000; for(int i=0;i<N;i++){ auto [xp, yp] = p[i]; int ok = 3000, ng = -1; while(ok - ng > 1){ int m = (ok + ng) / 2; int lx = std::lower_bound(std::begin(q), std::end(q), std::make_tuple(xp - m, std::numeric_limits<int>::min())) - std::begin(q); lx += numLeaves; int rx = std::upper_bound(std::begin(q), std::end(q), std::make_tuple(xp + m, std::numeric_limits<int>::max())) - std::begin(q); rx += numLeaves; bool can = false; for(;lx<rx;lx/=2,rx/=2){ if(lx & 1){ auto it = std::lower_bound(std::begin(seg[lx]), std::end(seg[lx]), yp - m); if(it != seg[lx].end() && *it <= yp + m){ can = true; break; } lx += 1; } if(rx & 1){ rx -= 1; auto it = std::lower_bound(std::begin(seg[rx]), std::end(seg[rx]), yp - m); if(it != seg[rx].end() && *it <= yp + m){ can = true; break; } } } if(can){ ok = m; }else{ ng = m; } } res = std::min(res, ok); } std::cout << res << std::endl; }