結果

問題 No.1874 Minimum of Sum of Rectangles
ユーザー CyanmondCyanmond
提出日時 2022-03-02 14:35:46
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 773 ms / 3,000 ms
コード長 6,655 bytes
コンパイル時間 2,810 ms
コンパイル使用メモリ 231,116 KB
実行使用メモリ 25,116 KB
最終ジャッジ日時 2023-10-19 05:47:24
合計ジャッジ時間 21,603 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 1 ms
4,348 KB
testcase_04 AC 3 ms
4,348 KB
testcase_05 AC 87 ms
5,696 KB
testcase_06 AC 91 ms
5,696 KB
testcase_07 AC 91 ms
5,696 KB
testcase_08 AC 84 ms
5,700 KB
testcase_09 AC 156 ms
5,632 KB
testcase_10 AC 157 ms
5,624 KB
testcase_11 AC 157 ms
5,636 KB
testcase_12 AC 161 ms
5,664 KB
testcase_13 AC 156 ms
5,568 KB
testcase_14 AC 748 ms
24,996 KB
testcase_15 AC 741 ms
25,060 KB
testcase_16 AC 738 ms
25,068 KB
testcase_17 AC 750 ms
25,060 KB
testcase_18 AC 746 ms
25,060 KB
testcase_19 AC 743 ms
25,056 KB
testcase_20 AC 720 ms
25,056 KB
testcase_21 AC 730 ms
25,060 KB
testcase_22 AC 720 ms
25,060 KB
testcase_23 AC 750 ms
25,056 KB
testcase_24 AC 756 ms
25,060 KB
testcase_25 AC 742 ms
25,060 KB
testcase_26 AC 751 ms
25,060 KB
testcase_27 AC 773 ms
25,056 KB
testcase_28 AC 768 ms
25,060 KB
testcase_29 AC 764 ms
25,060 KB
testcase_30 AC 757 ms
24,992 KB
testcase_31 AC 766 ms
25,116 KB
testcase_32 AC 766 ms
25,056 KB
testcase_33 AC 758 ms
25,060 KB
testcase_34 AC 2 ms
4,348 KB
testcase_35 AC 2 ms
4,348 KB
testcase_36 AC 2 ms
4,348 KB
testcase_37 AC 157 ms
5,628 KB
testcase_38 AC 157 ms
5,540 KB
testcase_39 AC 157 ms
5,624 KB
testcase_40 AC 161 ms
5,636 KB
testcase_41 AC 156 ms
5,544 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using i64 = int64_t;

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();

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

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

        std::vector<std::pair<int, int>> points;
        points.reserve(sx);
        for (int x = 0; x < sx; ++x) {
            for (const int i : events[x]) {
                auto v = seg.get(Y[i]);
                v.l -= x_p[X[i]];
                --v.cl;
                v.u += x_p[X[i]];
                ++v.cu;
                seg.set(Y[i], v);
            }

            const i64 all_sum = calc_sum(seg.fold(), x);

            auto f = [&](M1::Type v) {
                const i64 sum = calc_sum(v, x);
                return 2 * sum <= all_sum;
            };
            const int r = seg.calc_max_right(0, f);
            if (r == 0) {
                points.push_back({x, r});
            } else if (r == sy) {
                points.push_back({x, r - 1});
            } else {
                const i64 v1 = calc_sum(seg.fold(0, r), x),
                          v2 = calc_sum(seg.fold(0, r + 1), x);
                if (2 * v1 == all_sum)
                    points.push_back({x, r - 1});
                else
                    points.push_back({x, r});
            }
        }

        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(sy);
        SegmentTree<M3> seg_s(sy), seg_c(sy);
        std::vector<std::vector<int>> event_a(sx), event_q(sx);
        for (int i = 0; i < N; ++i) event_a[X[i]].push_back(i);
        for (int i = 0; i < M; ++i) event_q[points[i].first].push_back(i);

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

            for (const int i : event_q[x]) {
                const int y = points[i].second;
                i64 sum = (seg_c.fold(0, y) * x_p[x] - seg_s.fold(0, y)) * y_p[y];
                const auto f = seg_f.fold(0, y);
                sum -= x_p[x] * 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