結果

問題 No.738 平らな農地
ユーザー oshiborioshibori
提出日時 2018-10-01 03:48:09
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 192 ms / 2,000 ms
コード長 7,629 bytes
コンパイル時間 1,975 ms
コンパイル使用メモリ 178,332 KB
実行使用メモリ 10,368 KB
最終ジャッジ日時 2024-04-20 13:53:01
合計ジャッジ時間 11,393 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 4 ms
5,376 KB
testcase_06 AC 4 ms
5,376 KB
testcase_07 AC 4 ms
5,376 KB
testcase_08 AC 3 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 3 ms
5,376 KB
testcase_12 AC 3 ms
5,376 KB
testcase_13 AC 4 ms
5,376 KB
testcase_14 AC 3 ms
5,376 KB
testcase_15 AC 166 ms
9,600 KB
testcase_16 AC 166 ms
9,728 KB
testcase_17 AC 173 ms
9,728 KB
testcase_18 AC 167 ms
9,600 KB
testcase_19 AC 128 ms
10,112 KB
testcase_20 AC 178 ms
9,856 KB
testcase_21 AC 183 ms
9,984 KB
testcase_22 AC 179 ms
9,856 KB
testcase_23 AC 172 ms
9,856 KB
testcase_24 AC 153 ms
9,600 KB
testcase_25 AC 3 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 3 ms
5,376 KB
testcase_28 AC 3 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 2 ms
5,376 KB
testcase_31 AC 3 ms
5,376 KB
testcase_32 AC 2 ms
5,376 KB
testcase_33 AC 3 ms
5,376 KB
testcase_34 AC 2 ms
5,376 KB
testcase_35 AC 2 ms
5,376 KB
testcase_36 AC 3 ms
5,376 KB
testcase_37 AC 2 ms
5,376 KB
testcase_38 AC 2 ms
5,376 KB
testcase_39 AC 3 ms
5,376 KB
testcase_40 AC 3 ms
5,376 KB
testcase_41 AC 3 ms
5,376 KB
testcase_42 AC 3 ms
5,376 KB
testcase_43 AC 2 ms
5,376 KB
testcase_44 AC 3 ms
5,376 KB
testcase_45 AC 185 ms
10,240 KB
testcase_46 AC 173 ms
9,472 KB
testcase_47 AC 168 ms
9,984 KB
testcase_48 AC 162 ms
9,728 KB
testcase_49 AC 162 ms
9,600 KB
testcase_50 AC 171 ms
10,112 KB
testcase_51 AC 192 ms
10,240 KB
testcase_52 AC 175 ms
9,728 KB
testcase_53 AC 166 ms
9,856 KB
testcase_54 AC 183 ms
10,240 KB
testcase_55 AC 186 ms
10,112 KB
testcase_56 AC 183 ms
9,984 KB
testcase_57 AC 162 ms
9,728 KB
testcase_58 AC 173 ms
9,856 KB
testcase_59 AC 174 ms
10,368 KB
testcase_60 AC 169 ms
10,240 KB
testcase_61 AC 173 ms
9,984 KB
testcase_62 AC 168 ms
9,600 KB
testcase_63 AC 187 ms
10,240 KB
testcase_64 AC 174 ms
10,112 KB
testcase_65 AC 22 ms
9,600 KB
testcase_66 AC 23 ms
10,112 KB
testcase_67 AC 75 ms
9,600 KB
testcase_68 AC 77 ms
9,856 KB
testcase_69 AC 92 ms
9,984 KB
testcase_70 AC 85 ms
10,240 KB
testcase_71 AC 84 ms
10,112 KB
testcase_72 AC 71 ms
9,728 KB
testcase_73 AC 63 ms
9,728 KB
testcase_74 AC 96 ms
9,984 KB
testcase_75 AC 92 ms
9,600 KB
testcase_76 AC 91 ms
9,856 KB
testcase_77 AC 82 ms
9,728 KB
testcase_78 AC 94 ms
9,984 KB
testcase_79 AC 118 ms
10,240 KB
testcase_80 AC 106 ms
9,728 KB
testcase_81 AC 109 ms
9,728 KB
testcase_82 AC 105 ms
9,984 KB
testcase_83 AC 87 ms
10,240 KB
testcase_84 AC 86 ms
9,984 KB
testcase_85 AC 29 ms
10,240 KB
testcase_86 AC 32 ms
9,600 KB
testcase_87 AC 101 ms
9,856 KB
testcase_88 AC 91 ms
9,472 KB
testcase_89 AC 1 ms
5,376 KB
testcase_90 AC 2 ms
5,376 KB
testcase_91 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
#ifdef _DEBUG
#define _GLIBCXX_DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
typedef __int128_t Int;
#define DBG 1
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define loop(n) rep(loop, (0), (n))
#define all(c) begin(c), end(c)
const int INF =
    sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
using pii = pair<int, int>;
// template<class T> ostream &operator<<(ostream &os,T &t){dump(t);return os;}
template <typename T, typename S>
istream &operator>>(istream &is, pair<T, S> &p) {
  is >> p.first >> p.second;
  return is;
}
template <typename T> void printvv(const vector<vector<T>> &v) {
  cerr << endl;
  rep(i, 0, v.size()) rep(j, 0, v[i].size()) {
    if (typeid(v[i][j]) == typeid(INF) and v[i][j] == INF) {
      cerr << "INF";
    } else
      cerr << v[i][j];
    cerr << (j == v[i].size() - 1 ? '\n' : ' ');
  }
  cerr << endl;
}
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
  std::ostream::sentry s(dest);
  if (s) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = std::end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = std::end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(std::ios_base::badbit);
    }
  }
  return dest;
}

__int128 parse(string &s) {
  __int128 ret = 0;
  for (int i = 0; i < s.length(); i++)
    if ('0' <= s[i] && s[i] <= '9')
      ret = 10 * ret + s[i] - '0';
  return ret;
}

#ifndef _DEBUG
#define printvv(...)
#endif
void YES(bool f) { cout << (f ? "YES" : "NO") << endl; }
void Yes(bool f) { cout << (f ? "Yes" : "No") << endl; }
template <class T> bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T> bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class Val> struct Treap {
  struct Node {
    Val val, sum, mini;
    Node *left, *right;
    int pri;
    int size;
    Node(Val v, int p) : val(v), mini(v), pri(p), size(1), sum(v) {
      left = right = nullptr;
    }
  };
  int size(Node *t) { return !t ? 0 : t->size; }
  Val sum(Node *t) { return !t ? 0 : t->sum; }
  Val val(Node *t) {
    assert(t);
    return t->val;
  }
  Val mini(Node *t) { return !t ? INF : t->mini; }

  Node *root;
  Treap() : root(nullptr){};
  Treap(Node *root) : root(root) {}
  Treap(Treap l, Treap r) : root(merge(l.root, r.root)) {}
  int size() { return size(root); }
  // get --- k; 0-index
  Val operator[](int k) {
    assert(k < size());
    return at(root, k)->val;
  }
  Node *setroot(Node *rrr) { return root = rrr; }

  // 子が変わったときに必ず呼ぶ
  Node *update(Node *t) {
    if (!t)
      return t;
    t->size = size(t->left) + size(t->right) + 1;
    t->sum = sum(t->left) + sum(t->right) + t->val;
    t->mini = min({val(t), mini(t->left), mini(t->right)});
    return t;
  }

  Node *update(Node *t, int k, Val v) { return insertAt(eraseAt(t, k), k, v); }

  // [l,r)
  Val mini(Node *t, int l, int r) {
    if (!t)
      return INF;
    if (r <= l)
      return INF;
    if (r - l == size(t))
      return mini(t);
    else if (size(t->left) >= r)
      return mini(t->left, l, r);
    else if (size(t->left) < l)
      return mini(t->right, l - (size(t->left) + 1), r - (size(t->left) + 1));
    return min({val(t), mini(t->left, l, size(t->left)),
                mini(t->right, 0, r - (size(t->left) + 1))});
  }

  Node *merge(Node *l, Node *r) {
    if (!l)
      return r;
    if (!r)
      return l;
    if (l->pri > r->pri) {
      l->right = merge(l->right, r);
      return update(l);
    } else {
      r->left = merge(l, r->left);
      return update(r);
    }
  }

  // ([0, k), [k, n))
  pair<Node *, Node *> split(Node *t, int k) {
    if (!t)
      return pair<Node *, Node *>(nullptr, nullptr);
    if (k <= size(t->left)) {
      pair<Node *, Node *> s = split(t->left, k);
      t->left = s.second;
      return make_pair(s.first, update(t));
    } else {
      pair<Node *, Node *> s = split(t->right, k - size(t->left) - 1);
      t->right = s.first;
      return make_pair(update(t), s.second);
    }
  }
  pair<Node *, Node *> split(int k) { return split(root, k); }

  // [0,n)
  int lowerbound(Node *t, Val v) {
    if (!t)
      return 0;
    if (v <= val(t))
      return lowerbound(t->left, v);
    else
      return size(t->left) + 1 + lowerbound(t->right, v);
  }
  int lowerbound(Val v) { return lowerbound(root, v); }
  int upperbound(Node *t, Val v) {
    if (!t)
      return 0;
    if (v <= val(t))
      return size(t->left) + 1 + upperbound(t->right, v);
    else
      return upperbound(t->left, v);
  }
  int upperbound(Val v) { return upperbound(root, v); }
  int count(Val v) { return upperbound(v) - lowerbound(v); }

  Node *insertAt(Node *t, int k, Val v) {
    auto s = split(t, k);
    Node *m = new Node(v, rand());
    return root = update(merge(update(merge(s.first, m)), s.second));
  }
  Node *insertAt(int k, Val v) { return insertAt(root, k, v); }

  Node *insert(Val v) { return insertAt(root, lowerbound(root, v), v); }

  Node *eraseAt(Node *t, int k) {
    auto s1 = split(t, k);
    auto s2 = split(s1.second, 1);
    return root = update(merge(s1.first, s2.second));
  }
  Node *eraseAt(int k) { return eraseAt(root, k); }
  Node *erase(Val v) { return (contain(v) ? eraseAt(lowerbound(v)) : nullptr); }

  Node *at(Node *t, int k) {
    assert(size(t) > k);
    auto s = split(t, k);
    Node *ret = s.second;
    while (ret->left)
      ret = ret->left;
    root = merge(s.first, s.second);
    return ret;
  }

  Node *circularShift(Node *t, int l, int r) {
    Node *a, *b, *c, *d;
    tie(a, d) = split(t, r);
    tie(a, b) = split(a, l);
    tie(b, c) = split(b, r - l - 1);
    return root = merge(merge(a, merge(c, b)), d);
  }

  bool contain(const Val q) const {
    auto a = root;
    while (a != nullptr) {
      if (a->val == q)
        return true;
      else if (a->val < q)
        a = a->right;
      else
        a = a->left;
    }
    return false;
  }
};

// template <typename T> int g(typename Treap<T>::Node t) { return 5; }

template <class Val> ostream &operator<<(ostream &o, Treap<Val> t) {
  function<void(typename Treap<Val>::Node *)> rec =
      [&](typename Treap<Val>::Node *x) {
        if (!x)
          return;
        rec(x->left);
        o << x->val << " ";
        rec(x->right);
        return;
      };
  o << "[";
  rec(t.root);
  o << "]";
  return o;
}
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(12);

  int N, K;
  cin >> N >> K;
  vector<int> A(N);
  rep(i, 0, N) { cin >> A[i]; }

  Treap<int> t;
  int ans(INF);
  rep(i, 0, N) {
    if (i < K - 1)
      t.insert(A[i]);
    else if (i >= K - 1) {
      t.insert(A[i]);
      dump(t, A[i]);
      int c = t[K / 2];
      int n = K / 2, m = K - n;
      auto p = t.split(K / 2);
      int a = t.sum(p.fi), b = t.sum(p.se);
      dump(a, b, c, n, m);
      chmin(ans, c * n - a + b - c * m);
      dump(ans);
      t.setroot(t.merge(p.fi, p.se));
      dump(t, A[i - (K - 1)]);
      t.erase(A[i - (K - 1)]);
      dump(t, A[i - (K - 1)]);
    }
  }
  cout << ans << endl;

  return 0;
}
0