#201340 (C++14) No.738 平らな農地

提出ソース

結果

問題	No.738 平らな農地
ユーザー	しらっ亭
提出日時	2017-08-31 18:33:22
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	89 ms / 2,000 ms
コード長	2,955 bytes
コンパイル時間	1,939 ms
コンパイル使用メモリ	181,904 KB
実行使用メモリ	8,320 KB
最終ジャッジ日時	2024-11-06 16:41:21
合計ジャッジ時間	8,189 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	4 ms 5,248 KB
testcase_06	AC	3 ms 5,248 KB
testcase_07	AC	4 ms 5,248 KB
testcase_08	AC	3 ms 5,248 KB
testcase_09	AC	2 ms 5,248 KB
testcase_10	AC	2 ms 5,248 KB
testcase_11	AC	3 ms 5,248 KB
testcase_12	AC	2 ms 5,248 KB
testcase_13	AC	3 ms 5,248 KB
testcase_14	AC	2 ms 5,248 KB
testcase_15	AC	79 ms 5,760 KB
testcase_16	AC	80 ms 6,144 KB
testcase_17	AC	79 ms 5,248 KB
testcase_18	AC	79 ms 5,248 KB
testcase_19	AC	74 ms 5,248 KB
testcase_20	AC	80 ms 5,632 KB
testcase_21	AC	86 ms 5,504 KB
testcase_22	AC	81 ms 5,888 KB
testcase_23	AC	81 ms 5,248 KB
testcase_24	AC	77 ms 5,248 KB
testcase_25	AC	2 ms 5,248 KB
testcase_26	AC	3 ms 5,248 KB
testcase_27	AC	3 ms 5,248 KB
testcase_28	AC	3 ms 5,248 KB
testcase_29	AC	3 ms 5,248 KB
testcase_30	AC	2 ms 5,248 KB
testcase_31	AC	2 ms 5,248 KB
testcase_32	AC	3 ms 5,248 KB
testcase_33	AC	3 ms 5,248 KB
testcase_34	AC	2 ms 5,248 KB
testcase_35	AC	2 ms 5,248 KB
testcase_36	AC	3 ms 5,248 KB
testcase_37	AC	2 ms 5,248 KB
testcase_38	AC	2 ms 5,248 KB
testcase_39	AC	3 ms 5,248 KB
testcase_40	AC	2 ms 5,248 KB
testcase_41	AC	2 ms 5,248 KB
testcase_42	AC	2 ms 5,248 KB
testcase_43	AC	2 ms 5,248 KB
testcase_44	AC	3 ms 5,248 KB
testcase_45	AC	89 ms 6,400 KB
testcase_46	AC	80 ms 5,632 KB
testcase_47	AC	85 ms 6,272 KB
testcase_48	AC	81 ms 6,400 KB
testcase_49	AC	82 ms 6,400 KB
testcase_50	AC	83 ms 6,784 KB
testcase_51	AC	89 ms 6,016 KB
testcase_52	AC	83 ms 5,888 KB
testcase_53	AC	82 ms 6,016 KB
testcase_54	AC	85 ms 6,272 KB
testcase_55	AC	88 ms 6,016 KB
testcase_56	AC	85 ms 6,144 KB
testcase_57	AC	79 ms 5,888 KB
testcase_58	AC	84 ms 6,272 KB
testcase_59	AC	87 ms 6,656 KB
testcase_60	AC	85 ms 6,656 KB
testcase_61	AC	86 ms 6,656 KB
testcase_62	AC	80 ms 6,144 KB
testcase_63	AC	88 ms 6,144 KB
testcase_64	AC	85 ms 6,272 KB
testcase_65	AC	11 ms 5,248 KB
testcase_66	AC	12 ms 5,248 KB
testcase_67	AC	49 ms 6,016 KB
testcase_68	AC	51 ms 6,400 KB
testcase_69	AC	58 ms 5,760 KB
testcase_70	AC	60 ms 6,016 KB
testcase_71	AC	25 ms 5,248 KB
testcase_72	AC	32 ms 5,248 KB
testcase_73	AC	33 ms 5,888 KB
testcase_74	AC	31 ms 5,248 KB
testcase_75	AC	60 ms 5,376 KB
testcase_76	AC	58 ms 5,760 KB
testcase_77	AC	59 ms 5,248 KB
testcase_78	AC	64 ms 5,632 KB
testcase_79	AC	61 ms 5,760 KB
testcase_80	AC	58 ms 5,632 KB
testcase_81	AC	59 ms 5,504 KB
testcase_82	AC	58 ms 5,504 KB
testcase_83	AC	34 ms 5,248 KB
testcase_84	AC	36 ms 5,248 KB
testcase_85	AC	73 ms 5,376 KB
testcase_86	AC	67 ms 5,248 KB
testcase_87	AC	72 ms 8,320 KB
testcase_88	AC	66 ms 7,936 KB
testcase_89	AC	2 ms 5,248 KB
testcase_90	AC	2 ms 5,248 KB
testcase_91	AC	2 ms 5,248 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

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;
    --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 と、その座圧版を全部求めておく
  vector<int> medians(n - k + 1);
  {
    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 で、今注目している長さ k の区間で、座圧後に i になる値の、個数と合計を管理する
  BinaryIndexedTree0<int> ft_cnt(m);
  BinaryIndexedTree0<int64_t> ft_sum(m);

  int64_t ans = 1e18;

  for (int i = 0; i < n; i++) {  // O(n) 回ループ
    // 値を入れる
    int a = A[i];
    int c = compress(a);  // O(log N)
    ft_cnt.add(c, 1);  // O(log N)
    ft_sum.add(c, a);  // O(log N)

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

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

      // 区間内で median 未満の個数と総和を取得
      int lower_cnt = ft_cnt.sum(median_c);  // O(log N)
      int64_t lower_sum = ft_sum.sum(median_c);  // O(log N)

      // 区間内で median 以上の個数と総和を取得
      int higher_cnt = ft_cnt.sum(median_c, m);  // O(log N)
      int64_t higher_sum = ft_sum.sum(median_c, m);  // O(log N)

      int64_t inc_cost = median * lower_cnt - lower_sum;
      int64_t dec_cost = higher_sum - median * higher_cnt;
      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;
}

yukicoder

結果

テストケース

ソースコード