結果

問題 No.2436 Min Diff Distance
ユーザー fumofumofunifumofumofuni
提出日時 2023-08-18 23:26:53
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 4,558 bytes
コンパイル時間 2,428 ms
コンパイル使用メモリ 215,880 KB
実行使用メモリ 106,040 KB
最終ジャッジ日時 2024-05-06 06:12:15
合計ジャッジ時間 6,595 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 76 ms
38,480 KB
testcase_01 AC 74 ms
32,960 KB
testcase_02 AC 71 ms
32,832 KB
testcase_03 TLE -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;

class Range {
    struct Iter {
        int itr;
        constexpr Iter(const int pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept { ++itr; }
        constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
        constexpr int operator*() const noexcept { return itr; }
    };
    const Iter first, last;

  public:
    explicit constexpr Range(const int first, const int last) noexcept : first(first), last(std::max(first, last)) {}
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

constexpr Range rep(const int l, const int r) noexcept { return Range(l, r); }
constexpr Range rep(const int n) noexcept { return Range(0, n); }

constexpr int ceil_log2(const u64 x) {
    int e = 0;
    while (((u64)1 << e) < x) ++e;
    return e;
}

template <class G> class FenwickTree {
    using T = typename G::Type;

    int logn;
    std::vector<T> data;

  public:
    explicit FenwickTree(const int size = 0) {
        logn = ceil_log2(size + 1) - 1;
        data = std::vector<T>(size + 1, G::identity());
    }

    int size() const { return data.size() - 1; }

    void add(int i, const T& x) {
        assert(0 <= i and i < size());
        i += 1;
        while (i <= size()) {
            data[i] = G::operation(data[i], x);
            i += i & -i;
        }
    }

    T fold() const { return fold(0, size()); }
    T fold(int l, int r) const {
        assert(0 <= l and l <= r and r <= size());
        T ret = G::identity();
        while (l < r) {
            ret = G::operation(ret, data[r]);
            r -= r & -r;
        }
        while (r < l) {
            ret = G::operation(ret, G::inverse(data[l]));
            l -= l & -l;
        }
        return ret;
    }

    template <class F> int max_right(const F& f) const {
        assert(f(G::identity()));
        int i = 0;
        T sum = G::identity();
        for (int k = (1 << logn); k > 0; k >>= 1) {
            if (i + k <= size() && f(G::operation(sum, data[i + k]))) {
                sum = G::operation(sum, data[i += k]);
            }
        }
        return i;
    }
};

template <class T> struct SumGroup {
    using Type = T;
    static constexpr T identity() { return T(0); }
    static constexpr T operation(const T& l, const T& r) { return l + r; }
    static constexpr T inverse(const T& x) { return -x; }
};

using std::array;
using std::pair;
using std::tuple;
using std::vector;

constexpr int MAX = 200000;
constexpr int MAX2 = 2 * MAX + 1;
constexpr int LOG = ceil_log2(MAX2);

void main_() {
    int N;
    std::cin >> N;
    vector<vector<int>> pts(MAX2);
    int Q=N*2;
    vector<int> A(Q), B(Q), K(Q);
    for (int i = 0; i < N; ++i) {
        int x, y;
        std::cin >> x >> y;
        pts[x + y].push_back(x - y + MAX);
        A[i*2]=x+y;B[i*2]=x-y+MAX;K[i*2]=2;
        A[i*2+1]=x+y;B[i*2+1]=x-y+MAX;K[i*2+1]=N;
    }
    vector<int> ok(Q, 2 * MAX), ng(Q, 0), cnt(Q);
    vector<vector<tuple<int, int, int>>> add(MAX2), sub(MAX2);
    for (const int step : rep(LOG)) {
        std::fill(cnt.begin(), cnt.end(), 0);
        for (auto& v : add) v.clear();
        for (auto& v : sub) v.clear();
        for (const int i : rep(Q)) {
            const int k = (ok[i] + ng[i]) / 2;
            const int l = std::max(0, B[i] - k), r = std::min(2 * MAX, B[i] + k) + 1;
            sub[std::max(0, A[i] - k)].emplace_back(l, r, i);
            add[std::min(2 * MAX, A[i] + k)].emplace_back(l, r, i);
        }
        FenwickTree<SumGroup<int>> fen(MAX2);
        for (const int x : rep(0, MAX2)) {
            for (const auto& [l, r, q] : sub[x]) {
                cnt[q] -= fen.fold(l, r);
            }
            for (const int y : pts[x]) {
                fen.add(y, 1);
            }
            for (const auto& [l, r, q] : add[x]) {
                cnt[q] += fen.fold(l, r);
            }
        }
        for (const int i : rep(Q)) {
            const int md = (ok[i] + ng[i]) / 2;
            (cnt[i] >= K[i] ? ok[i] : ng[i]) = md;
        }
    }
    int ans=1e9;
    for(int i=0;i<N;i++){
        ans=std::min(ans,ok[i*2+1]-ok[i*2]);
        //std::cout << ok[i*2+1]-ok[i*2] << '\n';
    }
    std::cout << ans << '\n';
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    main_();
    return 0;
}
0