結果

問題 No.1874 Minimum of Sum of Rectangles
ユーザー colognecologne
提出日時 2022-03-14 11:21:10
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,677 bytes
コンパイル時間 5,217 ms
コンパイル使用メモリ 166,656 KB
実行使用メモリ 24,960 KB
最終ジャッジ日時 2024-09-19 21:18:30
合計ジャッジ時間 11,777 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 WA -
testcase_05 AC 65 ms
5,376 KB
testcase_06 AC 67 ms
5,376 KB
testcase_07 AC 67 ms
5,376 KB
testcase_08 WA -
testcase_09 AC 70 ms
5,376 KB
testcase_10 AC 72 ms
5,376 KB
testcase_11 AC 71 ms
5,376 KB
testcase_12 AC 72 ms
5,376 KB
testcase_13 AC 71 ms
5,376 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 AC 1 ms
5,376 KB
testcase_35 AC 2 ms
5,376 KB
testcase_36 AC 2 ms
5,376 KB
testcase_37 AC 70 ms
5,376 KB
testcase_38 AC 71 ms
5,376 KB
testcase_39 AC 72 ms
5,504 KB
testcase_40 AC 70 ms
5,376 KB
testcase_41 AC 67 ms
5,376 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 += 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