結果

問題 No.1874 Minimum of Sum of Rectangles
ユーザー CyanmondCyanmond
提出日時 2022-02-28 01:08:41
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 6,450 bytes
コンパイル時間 2,763 ms
コンパイル使用メモリ 228,824 KB
実行使用メモリ 18,636 KB
最終ジャッジ日時 2024-09-16 00:37:57
合計ジャッジ時間 14,657 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 RE -
testcase_04 AC 3 ms
5,376 KB
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 AC 154 ms
5,468 KB
testcase_10 AC 154 ms
5,504 KB
testcase_11 AC 155 ms
5,436 KB
testcase_12 AC 154 ms
5,376 KB
testcase_13 AC 155 ms
5,440 KB
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 AC 2 ms
5,376 KB
testcase_35 AC 2 ms
5,376 KB
testcase_36 RE -
testcase_37 AC 155 ms
5,460 KB
testcase_38 AC 156 ms
5,376 KB
testcase_39 AC 155 ms
5,440 KB
testcase_40 AC 154 ms
5,376 KB
testcase_41 AC 153 ms
5,504 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using i64 = int64_t;
constexpr i64 inf64 = 1500000000000000000;

template <typename T> void setmin(T &v, const T a) {
    if (v > a) v = a;
}

std::vector<int> press(std::vector<int> &vec) {
    auto p = vec;
    std::sort(p.begin(), p.end());
    p.erase(std::unique(p.begin(), p.end()), p.end());
    for (auto &e : vec) e = (int)(std::lower_bound(p.begin(), p.end(), e) - p.begin());
    return p;
}

template <class M> struct SegmentTree {
    using T = typename M::Type;
    int n, size;
    std::vector<T> data;

    SegmentTree(int n_) : n(n_) {
        size = 1;
        while (size < n) size <<= 1;
        data.assign(2 * size, M::id());
    }

    void set(int i, const T val) {
        assert(0 <= i and i < n);
        i += size;
        data[i] = val;
        while (i != 1) {
            i >>= 1;
            data[i] = M::op(data[2 * i], data[2 * i + 1]);
        }
    }

    T get(int i) {
        assert(0 <= i and i < n);
        i += size;
        return data[i];
    }

    T fold(int l, int r) {
        assert(0 <= l and l <= r and r <= n);
        T pl = M::id(), pr = M::id();
        for (l += size, r += size; l < r; l >>= 1, r >>= 1) {
            if (l & 1) pl = M::op(pl, data[l++]);
            if (r & 1) pr = M::op(data[--r], pr);
        }
        return M::op(pl, pr);
    }

    T fold() { return data[1]; }

    template <class F> int calc_max_right(int l, const F &f) {
        assert(0 <= l and l <= n);
        assert(f(M::id()));
        if (l == n) return n;
        l += size;
        T product = M::id();
        do {
            while (l % 2 == 0) l >>= 1;
            if (not f(M::op(product, data[l]))) {
                while (l < size) {
                    l <<= 1;
                    if (f(M::op(product, data[l]))) product = M::op(product, data[l++]);
                }
                return l - size;
            }
            product = M::op(product, data[l++]);
        } while ((l & -l) != l);
        return n;
    }
};

struct M1 {
    struct Type {
        i64 u;
        i64 l;
        int cu;
        int cl;
    };
    static Type op(const Type a, const Type b) {
        return {
            a.u + b.u,
            a.l + b.l,
            a.cu + b.cu,
            a.cl + b.cl,
        };
    }
    static Type id() { return {0, 0, 0, 0}; }
};

struct M2 {
    struct Type {
        i64 a;
        i64 b;
    };
    static Type op(const Type a, const Type b) { return {a.a + b.a, a.b + b.b}; }
    static Type id() { return {0, 0}; }
};

struct M3 {
    using Type = i64;
    static Type op(const Type a, const Type b) { return a + b; }
    static Type id() { return 0; }
};

constexpr int max_xy = 1000000;

int main() {
    int N;
    std::cin >> N;
    std::vector<int> X(N), Y(N);
    for (int i = 0; i < N; ++i) std::cin >> X[i] >> Y[i];

    auto get_list = [&]() {
        const auto x_p = press(X), y_p = press(Y);
        const int sx = (int)x_p.size(), sy = (int)y_p.size();

        std::vector<std::pair<int, int>> points;
        SegmentTree<M1> seg(sx);
        for (int i = 0; i < N; ++i)
            seg.set(X[i], M1::op(seg.get(X[i]), {0, y_p[Y[i]], 0, 1}));
        std::vector<std::vector<int>> events(sx);
        for (int i = 0; i < N; ++i) events[Y[i]].push_back(i);

        auto calc_sum = [&](const M1::Type v, const int y) {
            return (v.cu * y_p[y] - v.u) + (v.l - v.cl * y_p[y]);
        };

        for (int y = 0; y < sy; ++y) {
            for (const int i : events[y]) {
                auto v = seg.get(X[i]);
                v.l -= y_p[Y[i]];
                --v.cl;
                v.u += y_p[Y[i]];
                ++v.cu;
                seg.set(X[i], v);
            }

            const auto product = seg.fold();
            const i64 all_sum = calc_sum(product, y);

            auto f = [&](M1::Type v) {
                const i64 sum = calc_sum(v, y);
                return sum <= all_sum / 2;
            };
            const int max_right = seg.calc_max_right(0, f);
            if (max_right != 0) points.push_back({max_right - 1, y});
            if (max_right != sx) points.push_back({max_right, y});
        }

        for (int i = 0; i < N; ++i) {
            X[i] = x_p[X[i]];
            Y[i] = y_p[Y[i]];
        }
        for (auto &[x, y] : points) {
            x = x_p[x];
            y = y_p[y];
        }

        return points;
    };
    auto points = get_list();

    const int M = (int)points.size();
    std::vector<i64> res(M);

    auto rotate = [&]() {
        auto conv = [&](int &x, int &y) {
            const int nx = max_xy - y;
            const int ny = x;
            x = nx;
            y = ny;
        };

        for (int i = 0; i < N; ++i) conv(X[i], Y[i]);
        for (auto &[x, y] : points) conv(x, y);
    };

    auto run = [&]() {
        const auto x_p = press(X), y_p = press(Y);
        const int sx = (int)x_p.size(), sy = (int)y_p.size();
        for (auto &[x, y] : points) {
            x = (int)(std::lower_bound(x_p.begin(), x_p.end(), x) - x_p.begin());
            y = (int)(std::lower_bound(y_p.begin(), y_p.end(), y) - y_p.begin());
        }

        SegmentTree<M2> seg_f(sx);
        SegmentTree<M3> seg_s(sx), seg_c(sx);
        std::vector<std::vector<int>> event_a(sy), event_q(sy);
        for (int i = 0; i < N; ++i) event_a[Y[i]].push_back(i);
        for (int i = 0; i < M; ++i) event_q[points[i].second].push_back(i);

        for (int y = 0; y < sy; ++y) {
            for (const int i : event_a[y]) {
                const int x = X[i];
                seg_f.set(x, M2::op(seg_f.get(x), {x_p[x], -((i64)x_p[x] * y_p[y])}));
                seg_s.set(x, seg_s.get(x) + y_p[y]);
                seg_c.set(x, seg_c.get(x) + 1);
            }

            for (const int i : event_q[y]) {
                const int x = points[i].first;
                i64 sum = (seg_c.fold(0, x) * y_p[y] - seg_s.fold(0, x)) * x_p[x];
                const auto f = seg_f.fold(0, x);
                sum -= y_p[y] * f.a + f.b;
                res[i] += sum;
            }
        }

        for (int i = 0; i < N; ++i) {
            X[i] = x_p[X[i]];
            Y[i] = y_p[Y[i]];
        }
        for (auto &[x, y] : points) {
            x = x_p[x];
            y = y_p[y];
        }
    };

    for ([[maybe_unused]] int i = 0; i < 4; ++i) {
        run();
        rotate();
    }

    std::cout << *std::min_element(res.begin(), res.end()) << std::endl;
}
0