結果

問題 No.1874 Minimum of Sum of Rectangles
ユーザー cologne
提出日時 2022-03-14 11:22:16
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 323 ms / 3,000 ms
コード長 2,683 bytes
コンパイル時間 2,994 ms
コンパイル使用メモリ 166,784 KB
実行使用メモリ 24,960 KB
最終ジャッジ日時 2024-09-19 21:19:33
合計ジャッジ時間 10,496 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0