結果

問題 No.738 平らな農地
ユーザー risujirohrisujiroh
提出日時 2019-01-03 03:22:05
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 256 ms / 2,000 ms
コード長 6,354 bytes
コンパイル時間 1,941 ms
コンパイル使用メモリ 179,224 KB
実行使用メモリ 9,796 KB
最終ジャッジ日時 2023-08-14 15:54:34
合計ジャッジ時間 16,660 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,384 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 4 ms
4,380 KB
testcase_06 AC 5 ms
4,384 KB
testcase_07 AC 6 ms
4,380 KB
testcase_08 AC 3 ms
4,380 KB
testcase_09 AC 2 ms
4,384 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 3 ms
4,380 KB
testcase_12 AC 3 ms
4,380 KB
testcase_13 AC 5 ms
4,380 KB
testcase_14 AC 3 ms
4,376 KB
testcase_15 AC 225 ms
9,084 KB
testcase_16 AC 235 ms
9,168 KB
testcase_17 AC 237 ms
9,084 KB
testcase_18 AC 230 ms
9,076 KB
testcase_19 AC 162 ms
9,560 KB
testcase_20 AC 234 ms
9,224 KB
testcase_21 AC 250 ms
9,588 KB
testcase_22 AC 234 ms
9,208 KB
testcase_23 AC 239 ms
9,392 KB
testcase_24 AC 208 ms
9,340 KB
testcase_25 AC 3 ms
4,380 KB
testcase_26 AC 3 ms
4,376 KB
testcase_27 AC 3 ms
4,376 KB
testcase_28 AC 3 ms
4,376 KB
testcase_29 AC 3 ms
4,376 KB
testcase_30 AC 3 ms
4,376 KB
testcase_31 AC 2 ms
4,380 KB
testcase_32 AC 3 ms
4,376 KB
testcase_33 AC 3 ms
4,384 KB
testcase_34 AC 3 ms
4,380 KB
testcase_35 AC 2 ms
4,380 KB
testcase_36 AC 2 ms
4,380 KB
testcase_37 AC 2 ms
4,376 KB
testcase_38 AC 3 ms
4,380 KB
testcase_39 AC 3 ms
4,380 KB
testcase_40 AC 3 ms
4,380 KB
testcase_41 AC 3 ms
4,384 KB
testcase_42 AC 3 ms
4,380 KB
testcase_43 AC 2 ms
4,380 KB
testcase_44 AC 3 ms
4,380 KB
testcase_45 AC 243 ms
9,668 KB
testcase_46 AC 232 ms
9,016 KB
testcase_47 AC 239 ms
9,472 KB
testcase_48 AC 215 ms
9,196 KB
testcase_49 AC 217 ms
9,140 KB
testcase_50 AC 222 ms
9,360 KB
testcase_51 AC 256 ms
9,652 KB
testcase_52 AC 228 ms
9,268 KB
testcase_53 AC 233 ms
9,388 KB
testcase_54 AC 255 ms
9,796 KB
testcase_55 AC 243 ms
9,772 KB
testcase_56 AC 241 ms
9,340 KB
testcase_57 AC 228 ms
9,188 KB
testcase_58 AC 232 ms
9,392 KB
testcase_59 AC 253 ms
9,776 KB
testcase_60 AC 243 ms
9,604 KB
testcase_61 AC 247 ms
9,656 KB
testcase_62 AC 225 ms
9,036 KB
testcase_63 AC 256 ms
9,668 KB
testcase_64 AC 244 ms
9,608 KB
testcase_65 AC 23 ms
9,116 KB
testcase_66 AC 24 ms
9,400 KB
testcase_67 AC 78 ms
9,152 KB
testcase_68 AC 78 ms
9,340 KB
testcase_69 AC 100 ms
9,436 KB
testcase_70 AC 92 ms
9,712 KB
testcase_71 AC 69 ms
9,600 KB
testcase_72 AC 68 ms
9,024 KB
testcase_73 AC 70 ms
9,208 KB
testcase_74 AC 75 ms
9,344 KB
testcase_75 AC 100 ms
9,080 KB
testcase_76 AC 111 ms
9,300 KB
testcase_77 AC 85 ms
9,180 KB
testcase_78 AC 91 ms
9,652 KB
testcase_79 AC 174 ms
9,556 KB
testcase_80 AC 165 ms
9,300 KB
testcase_81 AC 160 ms
9,124 KB
testcase_82 AC 153 ms
9,472 KB
testcase_83 AC 94 ms
9,592 KB
testcase_84 AC 184 ms
9,484 KB
testcase_85 AC 31 ms
9,648 KB
testcase_86 AC 33 ms
9,360 KB
testcase_87 AC 147 ms
9,452 KB
testcase_88 AC 135 ms
9,140 KB
testcase_89 AC 1 ms
4,384 KB
testcase_90 AC 2 ms
4,376 KB
testcase_91 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using lint = long long int;
using ulint = unsigned long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T, class U> void assign(V<T>& v, int n, const U& a) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


template<class Int> Int rng(Int a, Int b) {
  static mt19937 mt(chrono::steady_clock().now().time_since_epoch().count());
  assert(a < b);
  return uniform_int_distribution<Int>(a, b - 1)(mt);
}

namespace RandomizedBinarySearchTree {
  using T = lint;
  T op(const T& lhs, const T& rhs) { return lhs + rhs; }
  T op(const T& lhs, const T& mhs, const T& rhs) { return op(op(lhs, mhs), rhs); }
  constexpr T e = 0;

  using U = int;
  constexpr U id = 0;
  T ap(const U& f, const T& x) { return f != id ? f : x; }
  U cp(const U& g, const U& f) { return g != id ? g : f; }

  struct Node;
  using Tree = Node*;
  struct Node {
    int sz = 0;
    T val = e, acc = e;
    U laz = id;
    bool rev = false;
    Tree cl = nullptr, cr = nullptr;
    Node() {} // nil
    Node(const T& val); // leaf
    Node(const T& val, const T& acc, const U& laz, bool rev, Tree cl, Tree cr) :
      sz(cl->sz + 1 + cr->sz), val(val), acc(acc), laz(laz), rev(rev), cl(cl), cr(cr) {}
  };
  Tree nil = new Node();
  Node::Node(const T& val) : sz(1), val(val), acc(val), cl(nil), cr(nil) {}

  Tree act(Tree t, const U& f) {
    if (t == nil) return t;
    t->val = ap(f, t->val);
    t->acc = ap(f, t->acc);
    t->laz = cp(f, t->laz);
    return t;
  }
  Tree reverse(Tree t) {
    if (t == nil) return t;
    swap(t->cl, t->cr);
    t->rev ^= true;
    return t;
  }
  Tree push(Tree t) {
    if (t->laz == id and !t->rev) return t;
    if (t->laz != id) {
      t->cl = act(t->cl, t->laz);
      t->cr = act(t->cr, t->laz);
      t->laz = id;
    }
    if (t->rev) {
      t->cl = reverse(t->cl);
      t->cr = reverse(t->cr);
      t->rev = false;
    }
    return t;
  }
  Tree update(Tree t) {
    t->sz = t->cl->sz + 1 + t->cr->sz;
    t->acc = op(t->cl->acc, t->val, t->cr->acc);
    return t;
  }

  template<class Itr> Tree build(Itr first, Itr last) {
    int n = distance(first, last);
    if (n == 0) return nil;
    Itr middle = next(first, n / 2);
    Tree cl = build(first, middle);
    Tree cr = build(next(middle), last);
    return new Node(*middle, op(cl->acc, *middle, cr->acc), id, false, cl, cr);
  }
  template<class Itr> Itr dump(Tree t, Itr res) {
    if (t == nil) return res;
    t = push(t);
    res = dump(t->cl, res);
    *res++ = t->val;
    res = dump(t->cr, res);
    return res;
  }
  Tree rebuild(Tree t) {
    V<T> v(t->sz);
    dump(t, begin(v));
    return build(begin(v), end(v));
  }

  Tree merge(Tree tl, Tree tr) {
    if (tr == nil) return tl;
    if (tl == nil) return tr;
    if (rng(0, tl->sz + tr->sz) < tl->sz) {
      tl = push(tl);
      tl->cr = merge(tl->cr, tr);
      return update(tl);
    } else {
      tr = push(tr);
      tr->cl = merge(tl, tr->cl);
      return update(tr);
    }
  }
  Tree merge(Tree tl, Tree tm, Tree tr) {
    return merge(merge(tl, tm), tr);
  }
  pair<Tree, Tree> split(Tree t, int i) {
    if (t == nil) return {nil, nil};
    t = push(t);
    if (i <= t->cl->sz) {
      Tree tl;
      tie(tl, t->cl) = split(t->cl, i);
      return {tl, update(t)};
    } else {
      Tree tr;
      tie(t->cr, tr) = split(t->cr, i - t->cl->sz - 1);
      return {update(t), tr};
    }
  }
  tuple<Tree, Tree, Tree> split(Tree t, int l, int r) {
    Tree tl, tm, tr;
    tie(tl, tr) = split(t, r);
    tie(tl, tm) = split(tl, l);
    return make_tuple(tl, tm, tr);
  }

  Tree insert(Tree t, int i, const T& val) {
    Tree tl, tr;
    tie(tl, tr) = split(t, i);
    return merge(tl, new Node(val), tr);
  }
  Tree erase(Tree t, int i) {
    Tree tl, tm, tr;
    tie(tl, tm, tr) = split(t, i, i + 1);
    return merge(tl, tr);
  }

  T get_val(Tree t, int i) {
    if (t == nil) return e;
    if (i == t->cl->sz) return t->val;
    t = push(t);
    if (i < t->cl->sz) return get_val(t->cl, i);
    else return get_val(t->cr, i - t->cl->sz - 1);
  }
  Tree set_val(Tree t, int i, const T& val) {
    if (t == nil) return t;
    t = push(t);
    if (i == t->cl->sz) {
      t->val = val;
      return update(t);
    }
    if (i < t->cl->sz) {
      t->cl = set_val(t->cl, i, val);
      return update(t);
    } else {
      t->cr = set_val(t->cr, i - t->cl->sz - 1, val);
      return update(t);
    }
  }

  T acc(Tree t, int l, int r) {
    if (t == nil or l <= 0 and t->sz <= r) return t->acc;
    t = push(t);
    T resl = l < t->cl->sz ? acc(t->cl, l, r) : e;
    T resr = t->cl->sz + 1 < r ? acc(t->cr, l - t->cl->sz - 1, r - t->cl->sz - 1) : e;
    T resm = l <= t->cl->sz and t->cl->sz < r ? t->val : e;
    return op(resl, resm, resr);
  }
  Tree act(Tree t, int l, int r, const U& f) {
    if (t == nil or l <= 0 and t->sz <= r) return act(t, f);
    t = push(t);
    if (l < t->cl->sz) t->cl = act(t->cl, l, r, f);
    if (t->cl->sz + 1 < r) t->cr = act(t->cr, l - t->cl->sz - 1, r - t->cl->sz - 1, f);
    if (l <= t->cl->sz and t->cl->sz < r) t->val = ap(f, t->val);
    return update(t);
  }
  Tree reverse(Tree t, int l, int r) {
    Tree tl, tm, tr;
    tie(tl, tm, tr) = split(t, l, r);
    tm = reverse(tm);
    return merge(tl, tm, tr);
  }

  int lower_bound(Tree t, const T& val) {
    if (t == nil) return 0;
    t = push(t);
    if (val <= t->val) return lower_bound(t->cl, val);
    else return t->cl->sz + 1 + lower_bound(t->cr, val);
  }
  Tree insert(Tree t, const T& val) {
    return insert(t, lower_bound(t, val), val);
  }
}

using namespace RandomizedBinarySearchTree;

int main() {
  cin.tie(nullptr); ios_base::sync_with_stdio(false);
  int n, k; cin >> n >> k;
  V<> a(n); for (int i = 0; i < n; ++i) cin >> a[i];
  Tree t = nil;
  for (int i = 0; i < k; ++i) {
    t = insert(t, a[i]);
  }
  lint res = 9e18;
  for (int i = k; i <= n; ++i) {
    lint mid = get_val(t, k / 2);
    lint curr = (k / 2 * mid - acc(t, 0, k / 2)) + (acc(t, k / 2, k) - (k - k / 2) * mid);
    res = min(res, curr);
    if (i == n) break;
    t = insert(t, a[i]);
    t = erase(t, lower_bound(t, a[i - k]));
  }
  cout << res << '\n';
}
0