結果
問題 | No.738 平らな農地 |
ユーザー | beet |
提出日時 | 2018-09-28 21:34:07 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 342 ms / 2,000 ms |
コード長 | 6,110 bytes |
コンパイル時間 | 2,036 ms |
コンパイル使用メモリ | 182,092 KB |
実行使用メモリ | 14,172 KB |
最終ジャッジ日時 | 2024-04-20 10:11:54 |
合計ジャッジ時間 | 14,925 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
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 | 5 ms
5,376 KB |
testcase_06 | AC | 6 ms
5,376 KB |
testcase_07 | AC | 6 ms
5,376 KB |
testcase_08 | AC | 4 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 | 2 ms
5,376 KB |
testcase_13 | AC | 5 ms
5,376 KB |
testcase_14 | AC | 3 ms
5,376 KB |
testcase_15 | AC | 177 ms
11,032 KB |
testcase_16 | AC | 178 ms
11,332 KB |
testcase_17 | AC | 200 ms
11,060 KB |
testcase_18 | AC | 198 ms
11,016 KB |
testcase_19 | AC | 233 ms
11,540 KB |
testcase_20 | AC | 191 ms
11,200 KB |
testcase_21 | AC | 228 ms
11,716 KB |
testcase_22 | AC | 184 ms
11,208 KB |
testcase_23 | AC | 224 ms
11,388 KB |
testcase_24 | AC | 226 ms
11,276 KB |
testcase_25 | AC | 3 ms
5,376 KB |
testcase_26 | AC | 3 ms
5,376 KB |
testcase_27 | AC | 3 ms
5,376 KB |
testcase_28 | AC | 3 ms
5,376 KB |
testcase_29 | AC | 4 ms
5,376 KB |
testcase_30 | AC | 3 ms
5,376 KB |
testcase_31 | AC | 3 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 | 3 ms
5,376 KB |
testcase_36 | AC | 3 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 | 3 ms
5,376 KB |
testcase_43 | AC | 3 ms
5,376 KB |
testcase_44 | AC | 3 ms
5,376 KB |
testcase_45 | AC | 203 ms
12,140 KB |
testcase_46 | AC | 185 ms
11,416 KB |
testcase_47 | AC | 193 ms
11,960 KB |
testcase_48 | AC | 172 ms
11,596 KB |
testcase_49 | AC | 173 ms
11,700 KB |
testcase_50 | AC | 169 ms
11,920 KB |
testcase_51 | AC | 187 ms
11,944 KB |
testcase_52 | AC | 177 ms
11,708 KB |
testcase_53 | AC | 181 ms
11,876 KB |
testcase_54 | AC | 190 ms
12,084 KB |
testcase_55 | AC | 201 ms
11,948 KB |
testcase_56 | AC | 188 ms
11,784 KB |
testcase_57 | AC | 184 ms
11,468 KB |
testcase_58 | AC | 186 ms
11,904 KB |
testcase_59 | AC | 194 ms
12,268 KB |
testcase_60 | AC | 186 ms
12,236 KB |
testcase_61 | AC | 188 ms
12,224 KB |
testcase_62 | AC | 172 ms
11,548 KB |
testcase_63 | AC | 199 ms
12,260 KB |
testcase_64 | AC | 188 ms
12,100 KB |
testcase_65 | AC | 244 ms
11,324 KB |
testcase_66 | AC | 259 ms
11,540 KB |
testcase_67 | AC | 175 ms
13,216 KB |
testcase_68 | AC | 175 ms
13,664 KB |
testcase_69 | AC | 235 ms
13,852 KB |
testcase_70 | AC | 209 ms
14,172 KB |
testcase_71 | AC | 78 ms
7,968 KB |
testcase_72 | AC | 98 ms
7,572 KB |
testcase_73 | AC | 86 ms
7,724 KB |
testcase_74 | AC | 101 ms
7,688 KB |
testcase_75 | AC | 228 ms
13,072 KB |
testcase_76 | AC | 197 ms
13,536 KB |
testcase_77 | AC | 238 ms
13,068 KB |
testcase_78 | AC | 266 ms
14,028 KB |
testcase_79 | AC | 248 ms
14,048 KB |
testcase_80 | AC | 204 ms
13,564 KB |
testcase_81 | AC | 219 ms
13,232 KB |
testcase_82 | AC | 227 ms
13,968 KB |
testcase_83 | AC | 92 ms
7,936 KB |
testcase_84 | AC | 90 ms
7,704 KB |
testcase_85 | AC | 342 ms
13,908 KB |
testcase_86 | AC | 295 ms
12,944 KB |
testcase_87 | AC | 147 ms
13,432 KB |
testcase_88 | AC | 139 ms
12,944 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 |
ソースコード
#include<bits/stdc++.h> using namespace std; using Int = long long; struct FullyIndexableDictionary{ Int len,blk; vector<Int> bit,sum; FullyIndexableDictionary(){} FullyIndexableDictionary(Int len) :len(len),blk((len+31)>>5),bit(blk,0),sum(blk,0){} void set(Int k){ bit[k>>5]|=1<<(k&31); } void build(){ sum[0]=0; for(Int i=1;i<blk;i++) sum[i]=sum[i-1]+__builtin_popcount(bit[i-1]); } bool operator[](Int k) const{ return bool((bit[k>>5]>>(k&31))&1); } Int rank(Int k){ return sum[k>>5]+__builtin_popcount(bit[k>>5]&((1<<(k&31))-1)); } Int rank(bool v,Int k){ return (v?rank(k):k-rank(k)); } Int select(bool v,Int k){ if(k<0||rank(v,len)<=k) return -1; Int low=0,high=len; while(low+1<high){ Int mid=(low+high)>>1; if(rank(v,mid)>=k+1) high=mid; else low=mid; } return high-1; } Int select(bool v,Int i,Int l){ return select(v,i+rank(v,l)); } }; template<class T,Int MAXLOG> struct WaveletMatrix{ Int len; FullyIndexableDictionary mat[MAXLOG]; Int zs[MAXLOG],buff1[MAXLOG],buff2[MAXLOG]; static const T npos=-1; Int freq_dfs(Int d,Int l,Int r,T val,T a,T b){ if(l==r) return 0; if(d==MAXLOG) return (a<=val&&val<b)?r-l:0; T nv=1ULL<<(MAXLOG-d-1)|val; T nnv=((1ULL<<(MAXLOG-d-1))-1)|nv; if(nnv<a||b<=val) return 0; if(a<=val&&nnv<b) return r-l; Int lc=mat[d].rank(1,l),rc=mat[d].rank(1,r); return freq_dfs(d+1,l-lc,r-rc,val,a,b) +freq_dfs(d+1,lc+zs[d],rc+zs[d],nv,a,b); } WaveletMatrix(vector<T> data){ len=data.size(); vector<T> l(len),r(len); for(Int dep=0;dep<MAXLOG;dep++){ mat[dep]=FullyIndexableDictionary(len+1); Int p=0,q=0; for(Int i=0;i<len;i++){ bool k=(data[i]>>(MAXLOG-(dep+1)))&1; if(k) r[q++]=data[i],mat[dep].set(i); else l[p++]=data[i]; } zs[dep]=p; mat[dep].build(); swap(l,data); for(Int i=0;i<q;i++) data[p+i]=r[i]; } } T access(Int k){ T res=0; bool bit; for(Int dep=0;dep<MAXLOG;dep++){ bit=mat[dep][k]; res=(res<<1)|bit; k=mat[dep].rank(bit,k)+zs[dep]*dep; } return res; } // return the number of v in [0,k) Int rank(T v,Int k){ Int l=0,r=k; for(Int dep=0;dep<MAXLOG;dep++){ buff1[dep]=l;buff2[dep]=r; bool bit=(v>>(MAXLOG-(dep+1)))&1; l=mat[dep].rank(bit,l)+zs[dep]*bit; r=mat[dep].rank(bit,r)+zs[dep]*bit; } return r-l; } // return the position of k-th v Int select(T v,Int k){ rank(v,len); for(Int dep=MAXLOG-1;dep>=0;dep--){ bool bit=(v>>(MAXLOG-(dep+1)))&1; k=mat[dep].select(bit,k,buff1[dep]); if(k>=buff2[dep]||k<0) return -1; k-=buff1[dep]; } return k; } Int select(T v,Int k,Int l){ return select(v,k+rank(v,l)); } // return k-th largest value in [l,r) T quantile(Int l,Int r,Int k){ if(r-l<=k||k<0) return -1; T res=0; for(Int dep=0;dep<MAXLOG;dep++){ Int p=mat[dep].rank(1,l); Int q=mat[dep].rank(1,r); if(q-p>k){ l=p+zs[dep]; r=q+zs[dep]; res|=(1<<(MAXLOG-(dep+1))); }else{ k-=(q-p); l-=p; r-=q; } } return res; } T rquantile(Int l,Int r,Int k){ return quantile(l,r,r-l-k-1); } // return number of points in [left, right) * [lower, upper) Int rangefreq(Int left,Int right,T lower,T upper){ return freq_dfs(0,left,right,0,lower,upper); } pair<Int, Int> ll(Int l,Int r,T v){ Int res=0; for(Int dep=0;dep<MAXLOG;dep++){ buff1[dep]=l;buff2[dep]=r; bool bit=(v>>(MAXLOG-(dep+1)))&1; if(bit) res+=r-l+mat[dep].rank(bit,l)-mat[dep].rank(bit,r); l=mat[dep].rank(bit,l)+zs[dep]*bit; r=mat[dep].rank(bit,r)+zs[dep]*bit; } return make_pair(res,r-l); } Int lt(Int l,Int r,T v){ auto p=ll(l,r,v); return p.first; } Int le(Int l,Int r,T v){ auto p=ll(l,r,v); return p.first+p.second; } T succ(Int l,Int r,T v){ Int k=le(l,r,v); return k==r-l?npos:rquantile(l,r,k); } T pred(Int l,Int r,T v){ Int k=lt(l,r,v); return k?rquantile(l,r,k-1):npos; } }; template<typename T> struct BIT{ Int n; vector<T> bit; //1-indexed BIT():n(-1){} BIT(Int n_,T d):n(n_),bit(n_+1,d){} T sum(Int i){ T s=bit[0]; for(Int x=i;x>0;x-=(x&-x)) s+=bit[x]; return s; } void add(Int i,T a){ if(i==0) return; for(Int x=i;x<=n;x+=(x&-x)) bit[x]+=a; } Int lower_bound(Int w){ if(w<=0) return 0; Int x=0,r=1; while(r<n) r<<=1; for(Int k=r;k>0;k>>=1){ if(x+k<=n&&bit[x+k]<w){ w-=bit[x+k]; x+=k; } } return x+1; } T sum0(Int i){ return sum(i+1); } void add0(Int i,T a){ add(i+1,a); } T query(Int l,Int r){ return sum(r-1)-sum(l-1); } T query0(Int l,Int r){ return sum(r)-sum(l); } }; template<typename T> vector<T> compress(vector<T> v){ sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); return v; } template<typename T> map<T, Int> dict(const vector<T> &v){ map<T, Int> res; for(Int i=0;i<(Int)v.size();i++) res[v[i]]=i; return res; } template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} //INSERT ABOVE HERE signed main(){ Int n,k; cin>>n>>k; vector<Int> a(n); for(Int i=0;i<n;i++) cin>>a[i]; WaveletMatrix<Int,32> wm(a); auto vx=compress(a); auto mx=dict(vx); BIT<Int> bit1(n+10,0),bit2(n+10,0); Int ans=1e18,sum=0; for(Int i=0;i<k;i++){ bit1.add0(mx[a[i]],1); bit2.add0(mx[a[i]],a[i]); sum+=a[i]; } for(Int i=0;i+k<=n;i++){ Int j=i+k; Int x=wm.quantile(i,j,k>>1); Int p=bit1.sum0(mx[x]),q=k-p; Int s=bit2.sum0(mx[x]); chmin(ans,p*x-s+(sum-s)-q*x); bit1.add0(mx[a[i]],-1); bit2.add0(mx[a[i]],-a[i]); sum-=a[i]; if(j==n) continue; bit1.add0(mx[a[j]],1); bit2.add0(mx[a[j]],a[j]); sum+=a[j]; } cout<<ans<<endl; return 0; }