結果

問題 No.2897 ２集合間距離
コンテスト
ユーザー tottoripaper
提出日時 2024-09-22 17:27:42
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,504 bytes
コンパイル時間 2,247 ms
コンパイル使用メモリ 207,860 KB
最終ジャッジ日時 2025-02-24 11:34:58
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19 WA * 5
権限があれば一括ダウンロードができます

ソースコード

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 = 0, ng = 3000;
        while(ng - ok > 1){
            int m = (ok + ng) / 2;

            int lx = std::upper_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::lower_bound(std::begin(q), std::end(q), std::make_tuple(xp + m, std::numeric_limits<int>::min())) - std::begin(q);
            rx += numLeaves;

            bool can = true;
            for(;lx<rx;lx/=2,rx/=2){
                if(lx & 1){
                    auto it = std::upper_bound(std::begin(seg[lx]), std::end(seg[lx]), yp - m);
                    if(it != seg[lx].end() && *it < yp + m){
                        can = false;
                        break;
                    }
                    lx += 1;
                }
                if(rx & 1){
                    rx -= 1;
                    auto it = std::upper_bound(std::begin(seg[rx]), std::end(seg[rx]), yp - m);
                    if(it != seg[rx].end() && *it < yp + m){
                        can = false;
                        break;
                    }
                }
            }

            if(can){
                ok = m;
            }else{
                ng = m;
            }
        }

        res = std::min(res, ok);
    }

    std::cout << res << std::endl;
}
0