結果

問題 No.738 平らな農地
ユーザー 0w1
提出日時 2018-10-10 02:51:15
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,608 bytes
コンパイル時間 3,172 ms
コンパイル使用メモリ 264,764 KB
最終ジャッジ日時 2025-01-06 14:30:13
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 12 WA * 30 TLE * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

template <class Node_CItr, class Node_Itr, class Cmp_Fn, class _Alloc>
struct node_update {
  typedef pair<int, int64_t> metadata_type; // (size, sum)
  Node_Itr find_by_order(int s) const {
    auto it = node_begin();
    while (it != node_end()) {
      auto l = it.get_l_child();
      auto r = it.get_r_child();
      int lsize = l == node_end() ? 0 : l.get_metadata().first;
      if (s < lsize) it = l;
      else if (s < lsize + (*it)->second) return it;
      else s -= lsize + (*it)->second, it = r;
    }
    return it;
  }
  int get_size() const { return node_begin().get_metadata().first; }
  int64_t get_sum() const { return node_begin().get_metadata().second; }
  void operator()(Node_Itr it, Node_CItr end_it) {
    auto l = it.get_l_child();
    auto r = it.get_r_child();
    pair<int, int64_t> left, right;
    if (l != end_it) left = l.get_metadata();
    if (r != end_it) right = r.get_metadata();
    const_cast<pair<int, int64_t> &>(it.get_metadata()) = make_pair(
        left.first + right.first + (*it)->second, left.second + right.second + 1LL * (*it)->first * (*it)->second);
  }
  virtual Node_CItr node_begin() const = 0;
  virtual Node_CItr node_end() const = 0;
};

typedef tree<pair<int, int>, null_type, less<pair<int, int64_t>>, rb_tree_tag, node_update> rbtree;

signed main() {
  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];

  rbtree t;
  for (int i = 0; i < K; ++i) {
    auto it = t.lower_bound({A[i], 0LL});
    if (it == t.end() || it->first != A[i]) {
      t.insert({A[i], 1LL});
    } else {
      t.insert({A[i], it->second + 1});
      t.erase(t.lower_bound({A[i], 0LL}));
    }
  }

  auto eval = [&](rbtree &t) {
    auto med = **t.find_by_order(t.get_size() / 2);
    rbtree right;
    t.split(med, right);
    int64_t res = 0;
    if (t.size()) res += 1LL * med.first * t.get_size() - t.get_sum();
    if (right.size()) res += right.get_sum() - 1LL * med.first * right.get_size();
    t.join(right);
    return res;
  };

  int64_t ans = eval(t);
  for (int i = 1; i + K <= N; ++i) {
    auto it = t.lower_bound({A[i - 1], 0LL});
    if (it->second > 1) t.insert({it->first, it->second - 1});
    else t.erase(it);
    it = t.lower_bound({A[i + K - 1], 0LL});
    if (it == t.end() || it->first != A[i + K - 1]) t.insert({A[i + K - 1], 1LL});
    else t.insert({it->first, it->second + 1}), t.erase({A[i + K - 1], 1LL});
    ans = min(ans, eval(t));
  }

  cout << ans << endl;
}
0