結果
問題 |
No.738 平らな農地
|
ユーザー |
![]() |
提出日時 | 2018-10-14 09:40:17 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 200 ms / 2,000 ms |
コード長 | 3,004 bytes |
コンパイル時間 | 878 ms |
コンパイル使用メモリ | 96,852 KB |
実行使用メモリ | 10,496 KB |
最終ジャッジ日時 | 2024-10-12 18:17:10 |
合計ジャッジ時間 | 11,526 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 87 |
ソースコード
#include <cstdio> #include <cstring> #include <string> #include <iostream> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <unordered_map> #include <unordered_set> #include <random> using namespace std; typedef long long int ll; typedef pair<int, int> P; random_device rnd; mt19937 mt(rnd()); uniform_real_distribution<> rnd1(0, 1.0); struct node_t{ ll val; ll sum; node_t *lch; node_t *rch; double pri; int cnt; node_t() {} node_t(ll v, double p):val(v), pri(p), cnt(1), sum(v), lch(nullptr), rch(nullptr){} }; int count(node_t *t){ return !t ? 0 : t->cnt; } ll sum(node_t *t){ return !t ? 0 : t->sum; } node_t *update(node_t *t){ t->cnt=count(t->lch)+count(t->rch)+1; t->sum=sum(t->lch)+sum(t->rch)+(t->val); return t; } node_t *merge(node_t *l, node_t *r){ if(!l || !r) return !l ? r : l; if(l->pri > r->pri){ l->rch=merge(l->rch, r); return update(l); }else{ r->lch=merge(l, r->lch); return update(r); } } pair<node_t*, node_t*> split(node_t *t, ll x){ if(!t) return make_pair(nullptr, nullptr); if(x <= t->val){ pair<node_t*, node_t*> s=split(t->lch, x); t->lch=s.second; return make_pair(s.first, update(t)); }else{ pair<node_t*, node_t*> s=split(t->rch, x); t->rch=s.first; return make_pair(update(t), s.second); } } pair<node_t*, node_t*> split2(node_t *t, int k){ //[0, k), [k,n) if(!t) return make_pair(nullptr, nullptr); if(k <= count(t->lch)){ pair<node_t*, node_t*> s=split2(t->lch, k); t->lch=s.second; return make_pair(s.first, update(t)); }else{ pair<node_t*, node_t*> s=split2(t->rch, k-1-count(t->lch)); t->rch=s.first; return make_pair(update(t), s.second); } } node_t *insert(node_t *t, ll x){ pair<node_t*, node_t*> s=split(t, x); return merge(merge(s.first, new node_t(x, rnd1(mt))), s.second); } node_t *erase(node_t *t, int k){ pair<node_t*, node_t*> s=split2(t, k); pair<node_t*, node_t*> s2=split2(s.second, 1); return merge(s.first, s2.second); } ll find(node_t *t, int k){ if(count(t->lch)==k){ return t->val; }else if(count(t->lch)<k){ return find(t->rch, k-count(t->lch)-1); }else{ return find(t->lch, k); } } void find2(node_t *t, ll x, int& ans){ if(x==(t->val)){ ans+=count(t->lch); return; }else if(x<(t->val)){ return find2(t->lch, x, ans); }else{ ans+=(count(t->lch)+1); return find2(t->rch, x, ans); } } ll calc(node_t *t, int k){ ll x=find(t, k); pair<node_t*, node_t*> s=split2(t, k); ll s1=sum(s.first), s2=sum(s.second); ll ans=x*(ll)k-s1+s2-x*(ll)(count(s.second)); t=merge(s.first, s.second); return ans; } int main() { int n, k; cin>>n>>k; ll a[100000]; for(int i=0; i<n; i++){ cin>>a[i]; } node_t *s=nullptr; for(int i=0; i<k; i++){ s=insert(s, a[i]); } ll ans=calc(s, k/2); for(int i=k; i<n; i++){ s=insert(s, a[i]); int ct=0; find2(s, a[i-k], ct); s=erase(s, ct); ans=min(ans, calc(s, k/2)); } cout<<ans<<endl; return 0; }