結果

問題 No.738 平らな農地
コンテスト
ユーザー 梧桐
提出日時 2026-02-23 20:46:14
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 211 ms / 2,000 ms
コード長 2,334 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,030 ms
コンパイル使用メモリ 88,684 KB
実行使用メモリ 37,676 KB
最終ジャッジ日時 2026-02-23 20:46:27
合計ジャッジ時間 11,745 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 87
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long LL;

const int N = 100010, V = 1000000010;
const LL INF = 9e18;

int n, k, a[N];
LL ans;

struct Node { int l, r, cnt; LL sum; };
struct SegTree {
    int rt, idx;
    Node seg[N * 100];
    void PushUp(int u) {
        seg[u].cnt = seg[seg[u].l].cnt + seg[seg[u].r].cnt;
        seg[u].sum = seg[seg[u].l].sum + seg[seg[u].r].sum;
    }
    void Add(int &u, int ul, int ur, int x, LL v) {
        if (u == 0) u = ++idx;
        if (ul == ur) {
            seg[u].cnt += v / abs(v);
            seg[u].sum += v;
            return;
        }
        int mid = ul + ur >> 1;
        if (x <= mid) Add(seg[u].l, ul, mid, x, v);
        else Add(seg[u].r, mid + 1, ur, x, v);
        PushUp(u);
    }
    Node Query(int u, int ul, int ur, int l, int r) {
        if (u == 0) return { 0, 0, 0, 0LL };
        if (l <= ul && ur <= r) return seg[u];
        Node ret = { 0, 0, 0, 0LL };
        int mid = ul + ur >> 1;
        if (mid >= l) {
            Node v1 = Query(seg[u].l, ul, mid, l, r);
            ret.cnt += v1.cnt, ret.sum += v1.sum;
        }
        if (mid + 1 <= r) {
            Node v2 = Query(seg[u].r, mid + 1, ur, l, r);
            ret.cnt += v2.cnt, ret.sum += v2.sum;
        }
        return ret;
    }
    int Kth(int u, int ul, int ur, int kth) {
        if (ul == ur) return ul;
        int mid = ul + ur >> 1;
        if (seg[seg[u].l].cnt >= kth) {
            return Kth(seg[u].l, ul, mid, kth);
        } else {
            return Kth(seg[u].r, mid + 1, ur, kth - seg[seg[u].l].cnt);
        }
    }
};
SegTree sgt;

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);

    ans = INF;
    for (int i = 1; i <= n; ++i) {
        if (i < k) sgt.Add(sgt.rt, 1, V, a[i], a[i]);
        else {
            sgt.Add(sgt.rt, 1, V, a[i], a[i]);
            if (i > k) sgt.Add(sgt.rt, 1, V, a[i - k], -a[i - k]);
            int median = sgt.Kth(sgt.rt, 1, V, (k + 1) / 2);
            Node r1 = sgt.Query(sgt.rt, 1, V, 1, median - 1);
            Node r2 = sgt.Query(sgt.rt, 1, V, 1, median);
            LL v = 1LL * r1.cnt * median - r1.sum + sgt.seg[sgt.rt].sum - r2.sum - 1LL * (k - r2.cnt) * median;
            ans = min(ans, v);
        }
    }
    printf("%lld\n", ans);

    return 0;
}
0