結果

問題 No.738 平らな農地
ユーザー しらっ亭
提出日時 2017-08-31 18:25:11
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 89 ms / 2,000 ms
コード長 2,909 bytes
コンパイル時間 2,117 ms
コンパイル使用メモリ 182,280 KB
実行使用メモリ 8,192 KB
最終ジャッジ日時 2024-11-06 16:41:13
合計ジャッジ時間 8,454 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 87
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using V = pair<int, int64_t>;

V operator+(const V &l, const V &r) {
  return {l.first + r.first, l.second + r.second};
}

V operator-(const V &l, const V &r) {
  return {l.first - r.first, l.second - r.second};
}

template <typename T> struct BinaryIndexedTree0 {
  const int N;
  vector<T> val;

  BinaryIndexedTree0(int N) : N(N), val(N) {}

  T sum(int i) const {
    T s = {0, 0};
    --i;
    if (i >= N) i = N - 1;
    for (; i >= 0; i = (i & (i + 1)) - 1) s = s + val[i];
    return s;
  }

  T sum(int l, int r) const {
    return sum(r) - sum(l);
  }

  void add(int i, T x) {
    for (; i < N; i |= i + 1) val[i] = val[i] + x;
  }

  void set(int i, T x) {
    T c = sum(i, i + 1);
    add(i, x - c);
  }
};

int64_t solve(const int n, const int k, const vector<int> &A) {
  if (k == 1) return 0;

  // 座圧の前準備
  vector<int> compressor(A);
  {
    sort(compressor.begin(), compressor.end());
    compressor.erase(unique(compressor.begin(), compressor.end()), compressor.end());
  }
  auto compress = [&compressor](int i) {
    return lower_bound(compressor.begin(), compressor.end(), i) - compressor.begin();
  };

  // 座圧した結果出てくる数字の種類数
  int m = compressor.size();

  // median と、その座圧版を全部求めておく
  int num_medians = n - k + 1;
  vector<int> medians(num_medians);
  {
    multiset<int> S(&A[0], &A[k]);
    auto it = next(S.begin(), k / 2);

    for (int i = k; i <= n; i++) {
      medians[i - k] = *it;
      S.insert(A[i]);
      if (A[i] <  *it) it--;
      if (A[i-k] <= *it) it++;
      S.erase(S.lower_bound(A[i-k]));
    }
  }

  // bit の i 番目には、今注目している長さ k の区間で、座圧後に i になる値の、個数と合計を入れている。
  // その range-sum ができるようになっている
  BinaryIndexedTree0<V> ft(m);

  int64_t ans = 1e18;

  for (int i = 0; i < n; i++) {
    // 値を入れる O(log N)
    int a = A[i];
    ft.add(compress(a), {1, a});

    // 範囲外に出たものを取り除く O(log N)
    if (i >= k) {
      int c = A[i-k];
      ft.add(compress(c), {-1, -c});
    }

    if (i >= k - 1) {
      int64_t median = medians[i-k+1];
      int median_c = compress(median);

      // 区間内で median 未満の個数と総和を取得
      V lower = ft.sum(median_c);
      // 区間内で median 以上の個数と総和を取得
      V higher = ft.sum(median_c, m);

      int64_t inc_cost = median * lower.first - lower.second;
      int64_t dec_cost = higher.second - median * higher.first;
      int64_t cand = inc_cost + dec_cost;

      ans = min(ans, cand);
    }
  }
  return ans;
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  int n, k; cin >> n >> k;
  vector<int> A(n);
  for (int i = 0; i < n; i++) cin >> A[i];

  cout << solve(n, k, A) << endl;

  return 0;
}
0