結果

問題 No.1874 Minimum of Sum of Rectangles
ユーザー 👑 colognecologne
提出日時 2022-03-14 11:22:16
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
AC  
実行時間 336 ms / 3,000 ms
コード長 2,683 bytes
コンパイル時間 3,022 ms
コンパイル使用メモリ 163,708 KB
実行使用メモリ 25,024 KB
最終ジャッジ日時 2023-10-20 01:30:18
合計ジャッジ時間 12,544 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 2 ms
4,348 KB
testcase_05 AC 67 ms
5,416 KB
testcase_06 AC 70 ms
5,416 KB
testcase_07 AC 70 ms
5,416 KB
testcase_08 AC 61 ms
5,416 KB
testcase_09 AC 76 ms
5,492 KB
testcase_10 AC 75 ms
5,484 KB
testcase_11 AC 76 ms
5,452 KB
testcase_12 AC 75 ms
5,512 KB
testcase_13 AC 75 ms
5,504 KB
testcase_14 AC 328 ms
25,024 KB
testcase_15 AC 329 ms
25,024 KB
testcase_16 AC 335 ms
25,024 KB
testcase_17 AC 336 ms
25,024 KB
testcase_18 AC 331 ms
25,024 KB
testcase_19 AC 329 ms
25,024 KB
testcase_20 AC 333 ms
25,024 KB
testcase_21 AC 331 ms
25,024 KB
testcase_22 AC 329 ms
25,024 KB
testcase_23 AC 328 ms
25,024 KB
testcase_24 AC 323 ms
25,024 KB
testcase_25 AC 329 ms
25,024 KB
testcase_26 AC 323 ms
25,024 KB
testcase_27 AC 326 ms
25,024 KB
testcase_28 AC 329 ms
25,024 KB
testcase_29 AC 324 ms
25,024 KB
testcase_30 AC 328 ms
25,024 KB
testcase_31 AC 321 ms
25,024 KB
testcase_32 AC 320 ms
25,024 KB
testcase_33 AC 327 ms
25,024 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 75 ms
5,512 KB
testcase_38 AC 76 ms
5,492 KB
testcase_39 AC 76 ms
5,492 KB
testcase_40 AC 75 ms
5,488 KB
testcase_41 AC 76 ms
5,452 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/lazysegtree>
using namespace std;

struct S
{
    long long dy, ysum, dxy, xysum, xsum;
};

S sum(S a, S b)
{
    a.dy += b.dy;
    a.ysum += b.ysum;
    a.dxy += b.dxy;
    a.xysum += b.xysum;
    a.xsum += b.xsum;
    return a;
}

S e()
{
    return {0LL, 0LL, 0LL, 0LL, 0LL};
}

using F = long long;

F id()
{
    return 0LL;
}

S mapping(F a, S b)
{
    b.ysum += b.dy * a;
    b.xysum += b.dxy * a;
    return b;
}

F composition(F a, F b)
{
    return a + b;
}

using Seg = atcoder::lazy_segtree<S, sum, e, F, mapping, composition, id>;

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

    vector<int> xc(X.begin(), X.end());
    sort(xc.begin(), xc.end());
    xc.erase(unique(xc.begin(), xc.end()), xc.end());
    for (int &x : X)
        x = lower_bound(xc.begin(), xc.end(), x) - xc.begin();

    vector<int> yc(Y.begin(), Y.end());
    sort(yc.begin(), yc.end());
    yc.erase(unique(yc.begin(), yc.end()), yc.end());
    vector<vector<int>> target(yc.size());
    for (int i = 0; i < N; i++)
    {
        Y[i] = lower_bound(yc.begin(), yc.end(), Y[i]) - yc.begin();
        target[Y[i]].push_back(i);
    }

    Seg seg(xc.size());
    // start with the case y = 0
    for (int i = 0; i < N; i++)
    {
        S val = seg.get(X[i]);
        if (Y[i] == 0)
            val.dy++, val.dxy += xc[X[i]];
        else
            val.dy--, val.dxy -= xc[X[i]];
        val.xsum += xc[X[i]];
        val.xysum += 1LL * xc[X[i]] * (yc[Y[i]] - yc[0]);
        val.ysum += (yc[Y[i]] - yc[0]);
        seg.set(X[i], val);
    }

    auto refresh = [&](int y)
    {
        seg.apply(0, (int)xc.size(), yc[y] - yc[y - 1]);
        for (int i : target[y])
        {
            S val = seg.get(X[i]);
            val.dy += 2;
            val.dxy += 2 * xc[X[i]];
            seg.set(X[i], val);
        }
    };

    auto calc = [&]()
    {
        long long total_y_sum = seg.all_prod().ysum;
        if (total_y_sum == 0)
            return 0LL;
        int target_xc = seg.max_right(0, [&](S s)
                                      { return 2 * s.ysum < total_y_sum; });

        S left_prod = seg.prod(0, target_xc);
        long long left_xy_sum = xc[target_xc] * left_prod.ysum - left_prod.xysum;
        S right_prod = seg.prod(target_xc, xc.size());
        long long right_xy_sum = right_prod.xysum - xc[target_xc] * right_prod.ysum;
        return left_xy_sum + right_xy_sum;
    };

    long long ans = calc();
    for (int i = 1; i < (int)yc.size(); ++i)
    {
        refresh(i);
        ans = min(ans, calc());
    }

    cout << ans << endl;
}
0