結果

問題 No.2897 2集合間距離
ユーザー tottoripapertottoripaper
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #

#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;
}
0