結果

問題 No.738 平らな農地
ユーザー 0w10w1
提出日時 2018-10-18 21:12:47
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 164 ms / 2,000 ms
コード長 6,337 bytes
コンパイル時間 2,634 ms
コンパイル使用メモリ 212,208 KB
実行使用メモリ 10,112 KB
最終ジャッジ日時 2024-04-24 19:45:52
合計ジャッジ時間 12,736 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 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 149 ms
9,368 KB
testcase_16 AC 148 ms
9,472 KB
testcase_17 AC 136 ms
9,472 KB
testcase_18 AC 137 ms
9,216 KB
testcase_19 AC 101 ms
9,984 KB
testcase_20 AC 148 ms
9,344 KB
testcase_21 AC 147 ms
9,856 KB
testcase_22 AC 148 ms
9,632 KB
testcase_23 AC 136 ms
9,728 KB
testcase_24 AC 122 ms
9,600 KB
testcase_25 AC 3 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 3 ms
5,376 KB
testcase_29 AC 3 ms
5,376 KB
testcase_30 AC 2 ms
5,376 KB
testcase_31 AC 2 ms
5,376 KB
testcase_32 AC 3 ms
5,376 KB
testcase_33 AC 3 ms
5,376 KB
testcase_34 AC 3 ms
5,376 KB
testcase_35 AC 2 ms
5,376 KB
testcase_36 AC 2 ms
5,376 KB
testcase_37 AC 3 ms
5,376 KB
testcase_38 AC 3 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 2 ms
5,376 KB
testcase_43 AC 3 ms
5,376 KB
testcase_44 AC 2 ms
5,376 KB
testcase_45 AC 156 ms
9,984 KB
testcase_46 AC 147 ms
9,344 KB
testcase_47 AC 153 ms
9,728 KB
testcase_48 AC 140 ms
9,488 KB
testcase_49 AC 141 ms
9,472 KB
testcase_50 AC 152 ms
9,600 KB
testcase_51 AC 159 ms
9,728 KB
testcase_52 AC 142 ms
9,344 KB
testcase_53 AC 151 ms
9,472 KB
testcase_54 AC 164 ms
9,728 KB
testcase_55 AC 158 ms
9,880 KB
testcase_56 AC 158 ms
9,728 KB
testcase_57 AC 145 ms
9,344 KB
testcase_58 AC 155 ms
9,856 KB
testcase_59 AC 156 ms
10,112 KB
testcase_60 AC 153 ms
9,728 KB
testcase_61 AC 156 ms
9,856 KB
testcase_62 AC 143 ms
9,496 KB
testcase_63 AC 160 ms
9,856 KB
testcase_64 AC 153 ms
9,856 KB
testcase_65 AC 25 ms
9,472 KB
testcase_66 AC 26 ms
9,856 KB
testcase_67 AC 72 ms
9,344 KB
testcase_68 AC 72 ms
9,600 KB
testcase_69 AC 92 ms
9,600 KB
testcase_70 AC 86 ms
9,984 KB
testcase_71 AC 48 ms
9,856 KB
testcase_72 AC 64 ms
9,348 KB
testcase_73 AC 70 ms
9,472 KB
testcase_74 AC 59 ms
9,856 KB
testcase_75 AC 88 ms
9,344 KB
testcase_76 AC 86 ms
9,600 KB
testcase_77 AC 82 ms
9,216 KB
testcase_78 AC 90 ms
9,984 KB
testcase_79 AC 119 ms
9,984 KB
testcase_80 AC 108 ms
9,600 KB
testcase_81 AC 95 ms
9,472 KB
testcase_82 AC 94 ms
9,600 KB
testcase_83 AC 82 ms
9,856 KB
testcase_84 AC 81 ms
9,600 KB
testcase_85 AC 32 ms
9,984 KB
testcase_86 AC 33 ms
9,216 KB
testcase_87 AC 100 ms
9,728 KB
testcase_88 AC 94 ms
9,344 KB
testcase_89 AC 2 ms
5,376 KB
testcase_90 AC 2 ms
5,376 KB
testcase_91 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

mt19937 rng((unsigned int)chrono::steady_clock::now().time_since_epoch().count());

class node {
 public:
  int id;
  node* l;
  node* r;
  node* p;
  bool rev;
  int sz;
  // declare extra variables:
  int P;
  int64_t sum;

  node(int _id) {
    id = _id;
    l = r = p = NULL;
    rev = false;
    sz = 1;
    // init extra variables:
    P = rng();
    sum = id;
  }

  void unsafe_reverse() {
    rev ^= 1;
    swap(l, r);
    pull();
  }

  // apply changes:
  void unsafe_apply() {}

  void push() {
    if (rev) {
      if (l != NULL) {
        l->unsafe_reverse();
      }
      if (r != NULL) {
        r->unsafe_reverse();
      }
      rev = 0;
    }
    // now push everything else:
  }

  void pull() {
    sz = 1;
    sum = id;
    // now init from self:

    if (l != NULL) {
      l->p = this;
      sz += l->sz;
      // now pull from l:
      sum += l->sum;
    }
    if (r != NULL) {
      r->p = this;
      sz += r->sz;
      // now pull from r:
      sum += r->sum;
    }
  }
};

void debug_node(node* v, string pref = "") {
#ifdef LOCAL
  if (v != NULL) {
    debug_node(v->r, pref + " ");
    cerr << pref << "-"
         << " " << v->id << '\n';
    debug_node(v->l, pref + " ");
  } else {
    cerr << pref << "-"
         << " "
         << "NULL" << '\n';
  }
#endif
}

namespace treap {
pair<node*, int> find(node* v, const function<int(node*)>& go_to) {
  // go_to returns: 0 -- found; -1 -- go left; 1 -- go right
  // find returns the last vertex on the descent and its go_to
  if (v == NULL) {
    return {NULL, 0};
  }
  int dir;
  while (true) {
    v->push();
    dir = go_to(v);
    if (dir == 0) {
      break;
    }
    node* u = (dir == -1 ? v->l : v->r);
    if (u == NULL) {
      break;
    }
    v = u;
  }
  return {v, dir};
}

node* get_leftmost(node* v) {
  return find(v, [&](node*) { return -1; }).first;
}

node* get_rightmost(node* v) {
  return find(v, [&](node*) { return 1; }).first;
}

node* get_kth(node* v, int k) {  // 0-indexed
  pair<node*, int> p = find(v, [&](node* u) {
    if (u->l != NULL) {
      if (u->l->sz > k) {
        return -1;
      }
      k -= u->l->sz;
    }
    if (k == 0) {
      return 0;
    }
    k--;
    return 1;
  });
  return (p.second == 0 ? p.first : NULL);
}

int get_position(node* v) {  // 0-indexed
  int k = (v->l != NULL ? v->l->sz : 0);
  while (v->p != NULL) {
    if (v == v->p->r) {
      k++;
      if (v->p->l != NULL) {
        k += v->p->l->sz;
      }
    }
    v = v->p;
  }
  return k;
}

node* get_bst_root(node* v) {
  while (v->p != NULL) {
    v = v->p;
  }
  return v;
}

pair<node*, node*> split(node* v, const function<bool(node*)>& is_right) {
  if (v == NULL) {
    return {NULL, NULL};
  }
  v->push();
  if (is_right(v)) {
    pair<node*, node*> p = split(v->l, is_right);
    if (p.first != NULL) {
      p.first->p = NULL;
    }
    v->l = p.second;
    v->pull();
    return {p.first, v};
  } else {
    pair<node*, node*> p = split(v->r, is_right);
    v->r = p.first;
    if (p.second != NULL) {
      p.second->p = NULL;
    }
    v->pull();
    return {v, p.second};
  }
}

pair<node*, node*> split_leftmost_k(node* v, int k) {
  return split(v, [&](node* u) {
    int left_and_me = (u->l != NULL ? u->l->sz : 0) + 1;
    if (k >= left_and_me) {
      k -= left_and_me;
      return false;
    }
    return true;
  });
}

node* merge(node* v, node* u) {
  if (v == NULL) {
    return u;
  }
  if (u == NULL) {
    return v;
  }
  if (v->P > u->P) {
    //    if (rng() % (v->sz + u->sz) < (unsigned int) v->sz) {
    v->push();
    v->r = merge(v->r, u);
    v->pull();
    return v;
  } else {
    u->push();
    u->l = merge(v, u->l);
    u->pull();
    return u;
  }
}

int count_left(node* v, const function<bool(node*)>& is_right) {
  if (v == NULL) {
    return 0;
  }
  v->push();
  if (is_right(v)) {
    return count_left(v->l, is_right);
  }
  return (v->l != NULL ? v->l->sz : 0) + 1 + count_left(v->r, is_right);
}

node* add(node* r, node* v, const function<bool(node*)>& go_left) {
  pair<node*, node*> p = split(r, go_left);
  return merge(p.first, merge(v, p.second));
}

node* remove(node* v) {  // returns the new root
  v->push();
  node* x = v->l;
  node* y = v->r;
  node* p = v->p;
  v->l = v->r = v->p = NULL;
  v->push();
  v->pull();  // now v might be reusable...
  node* z = merge(x, y);
  if (p == NULL) {
    if (z != NULL) {
      z->p = NULL;
    }
    return z;
  }
  if (p->l == v) {
    p->l = z;
  }
  if (p->r == v) {
    p->r = z;
  }
  while (true) {
    p->push();
    p->pull();
    if (p->p == NULL) {
      break;
    }
    p = p->p;
  }
  return p;
}

node* next(node* v) {
  if (v->r == NULL) {
    while (v->p != NULL && v->p->r == v) {
      v = v->p;
    }
    return v->p;
  }
  v->push();
  v = v->r;
  while (v->l != NULL) {
    v->push();
    v = v->l;
  }
  return v;
}

node* prev(node* v) {
  if (v->l == NULL) {
    while (v->p != NULL && v->p->l == v) {
      v = v->p;
    }
    return v->p;
  }
  v->push();
  v = v->l;
  while (v->r != NULL) {
    v->push();
    v = v->r;
  }
  return v;
}

int get_size(node* v) { return (v != NULL ? v->sz : 0); }

template <typename... T>
void apply(node* v, T... args) {
  v->unsafe_apply(args...);
}

void reverse(node* v) { v->unsafe_reverse(); }
}  // namespace treap

using namespace treap;

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];

  node* root = nullptr;
  for (int i = 0; i < K; ++i)
    root = add(root, new node(A[i]), [&](node* v) { return A[i] < v->id; });

  auto eval = [](node* &r) {
    assert(r);
    node* lc;
    node* rc;
    int med = get_kth(r, r->sz / 2)->id;
    tie(lc, rc) = split(r, [&](node* v) { return v->id > med; });
    int64_t ret = 0;
    if (lc) ret += 1LL * med * lc->sz - lc->sum;
    if (rc) ret += rc->sum - 1LL * med * rc->sz;
    r = merge(lc, rc);
    return ret;
  };

  int64_t ans = eval(root);
  for (int i = 1; i + K <= N; ++i) {
    root = remove(find(root, [&](node* v) {
      return (v->id != A[i - 1]) * (A[i - 1] < v->id ? -1 : +1); }).first);
    root = add(root, new node(A[i + K - 1]), [&](node* v) { return A[i + K - 1] < v->id; });
    ans = min(ans, eval(root));
  }
  cout << ans << endl;
}
0