結果

問題 No.2897 ２集合間距離
ユーザー tottoripapertottoripaper
提出日時 2024-09-22 17:59:19
言語 C++17
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,812 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 3 ms
6,944 KB
testcase_13 AC 5 ms
6,944 KB
testcase_14 AC 28 ms
6,944 KB
testcase_15 AC 45 ms
6,944 KB
testcase_16 AC 1,344 ms
43,496 KB
testcase_17 AC 1,337 ms
43,372 KB
testcase_18 AC 1,355 ms
43,368 KB
testcase_19 AC 1,375 ms
43,492 KB
testcase_20 AC 1,395 ms
43,368 KB
testcase_21 AC 1,215 ms
43,368 KB
testcase_22 AC 1,044 ms
43,496 KB
testcase_23 AC 2,058 ms
43,368 KB
権限があれば一括ダウンロードができます

ソースコード

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