結果
問題 | No.738 平らな農地 |
ユーザー | はむこ |
提出日時 | 2017-08-29 11:42:38 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 422 ms / 2,000 ms |
コード長 | 7,385 bytes |
コンパイル時間 | 1,596 ms |
コンパイル使用メモリ | 166,956 KB |
実行使用メモリ | 55,168 KB |
最終ジャッジ日時 | 2024-11-06 09:36:48 |
合計ジャッジ時間 | 21,283 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 58 ms
54,912 KB |
testcase_01 | AC | 57 ms
55,040 KB |
testcase_02 | AC | 57 ms
55,040 KB |
testcase_03 | AC | 57 ms
55,040 KB |
testcase_04 | AC | 58 ms
55,040 KB |
testcase_05 | AC | 65 ms
55,168 KB |
testcase_06 | AC | 66 ms
55,040 KB |
testcase_07 | AC | 64 ms
55,168 KB |
testcase_08 | AC | 61 ms
55,040 KB |
testcase_09 | AC | 60 ms
55,040 KB |
testcase_10 | AC | 58 ms
55,168 KB |
testcase_11 | AC | 61 ms
54,912 KB |
testcase_12 | AC | 59 ms
55,168 KB |
testcase_13 | AC | 63 ms
54,912 KB |
testcase_14 | AC | 59 ms
55,168 KB |
testcase_15 | AC | 244 ms
55,040 KB |
testcase_16 | AC | 248 ms
55,040 KB |
testcase_17 | AC | 293 ms
55,168 KB |
testcase_18 | AC | 282 ms
55,168 KB |
testcase_19 | AC | 340 ms
55,040 KB |
testcase_20 | AC | 253 ms
55,168 KB |
testcase_21 | AC | 314 ms
55,168 KB |
testcase_22 | AC | 261 ms
55,040 KB |
testcase_23 | AC | 315 ms
54,912 KB |
testcase_24 | AC | 324 ms
55,168 KB |
testcase_25 | AC | 59 ms
55,040 KB |
testcase_26 | AC | 59 ms
55,040 KB |
testcase_27 | AC | 60 ms
54,912 KB |
testcase_28 | AC | 59 ms
55,040 KB |
testcase_29 | AC | 61 ms
55,168 KB |
testcase_30 | AC | 59 ms
55,168 KB |
testcase_31 | AC | 59 ms
55,040 KB |
testcase_32 | AC | 61 ms
54,912 KB |
testcase_33 | AC | 64 ms
55,040 KB |
testcase_34 | AC | 59 ms
55,168 KB |
testcase_35 | AC | 59 ms
55,040 KB |
testcase_36 | AC | 58 ms
54,912 KB |
testcase_37 | AC | 59 ms
55,168 KB |
testcase_38 | AC | 59 ms
54,912 KB |
testcase_39 | AC | 60 ms
55,040 KB |
testcase_40 | AC | 60 ms
55,040 KB |
testcase_41 | AC | 59 ms
55,040 KB |
testcase_42 | AC | 58 ms
55,168 KB |
testcase_43 | AC | 59 ms
55,040 KB |
testcase_44 | AC | 59 ms
55,040 KB |
testcase_45 | AC | 235 ms
55,168 KB |
testcase_46 | AC | 238 ms
55,040 KB |
testcase_47 | AC | 229 ms
55,040 KB |
testcase_48 | AC | 207 ms
55,168 KB |
testcase_49 | AC | 203 ms
55,168 KB |
testcase_50 | AC | 205 ms
55,040 KB |
testcase_51 | AC | 246 ms
55,040 KB |
testcase_52 | AC | 225 ms
55,040 KB |
testcase_53 | AC | 230 ms
55,040 KB |
testcase_54 | AC | 243 ms
55,040 KB |
testcase_55 | AC | 248 ms
55,040 KB |
testcase_56 | AC | 240 ms
54,912 KB |
testcase_57 | AC | 226 ms
55,168 KB |
testcase_58 | AC | 230 ms
55,168 KB |
testcase_59 | AC | 225 ms
55,040 KB |
testcase_60 | AC | 214 ms
55,168 KB |
testcase_61 | AC | 223 ms
55,168 KB |
testcase_62 | AC | 219 ms
55,040 KB |
testcase_63 | AC | 249 ms
54,912 KB |
testcase_64 | AC | 233 ms
55,040 KB |
testcase_65 | AC | 363 ms
55,040 KB |
testcase_66 | AC | 374 ms
55,040 KB |
testcase_67 | AC | 275 ms
54,912 KB |
testcase_68 | AC | 268 ms
55,168 KB |
testcase_69 | AC | 385 ms
55,168 KB |
testcase_70 | AC | 315 ms
55,040 KB |
testcase_71 | AC | 283 ms
55,168 KB |
testcase_72 | AC | 242 ms
55,040 KB |
testcase_73 | AC | 228 ms
55,168 KB |
testcase_74 | AC | 294 ms
55,168 KB |
testcase_75 | AC | 356 ms
55,168 KB |
testcase_76 | AC | 284 ms
55,168 KB |
testcase_77 | AC | 390 ms
55,168 KB |
testcase_78 | AC | 422 ms
55,040 KB |
testcase_79 | AC | 398 ms
55,040 KB |
testcase_80 | AC | 311 ms
55,040 KB |
testcase_81 | AC | 358 ms
55,040 KB |
testcase_82 | AC | 361 ms
55,040 KB |
testcase_83 | AC | 262 ms
55,168 KB |
testcase_84 | AC | 239 ms
55,040 KB |
testcase_85 | AC | 407 ms
55,168 KB |
testcase_86 | AC | 378 ms
55,168 KB |
testcase_87 | AC | 115 ms
55,040 KB |
testcase_88 | AC | 112 ms
55,168 KB |
testcase_89 | AC | 56 ms
55,040 KB |
testcase_90 | AC | 58 ms
55,040 KB |
testcase_91 | AC | 58 ms
55,040 KB |
ソースコード
#include <bits/stdc++.h>#include <sys/time.h>using namespace std;#define rep(i,n) for(long long i = 0; i < (long long)(n); i++)template<class T1, class T2> bool chmin(T1 &a, T2 b) { return b < a && (a = b, true); }template<class T1, class T2> bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }using ll = long long; using vll = vector<ll>; using vvll = vector<vll>; using P = pair<ll, ll>;static const long long INF = 1e18;/*****************/// Dictionary/*****************/// Nはバケット数template<int N> class FID {static const int bucket = 512, block = 16;// 整数iのpopcountをO(1)で求めるためのテーブル// popcount[i] = __builtin_popcount(i), i<65536static char popcount[];// B[i]: s[0:512*i)のビット1の総数int n, B[N/bucket+10];// bs[i]: s[16*i:16*(i+1)]のビット列そのものunsigned short bs[N/block+10] = {};// b[i]: s[i/32*512:i/32*512+i%32*32)のビット1の総数// bs[i]を512bitずつリセットしながら、累積和を取ってる感じ。unsigned short b[N/block+10] = {};public:FID(){}FID(int n, bool s[]) : n(n) {if(!popcount[1]) for (int i = 0; i < (1<<block); i++) popcount[i] = __builtin_popcount(i);bs[0] = B[0] = b[0] = 0;for (int i = 0; i < n; i++) {if(i%block == 0) {bs[i/block+1] = 0;if(i%bucket == 0) {B[i/bucket+1] = B[i/bucket];b[i/block+1] = b[i/block] = 0;}else b[i/block+1] = b[i/block];}bs[i/block] |= short(s[i])<<(i%block);b[i/block+1] += s[i];B[i/bucket+1] += s[i];}if(n%bucket == 0) b[n/block] = 0;}// number of val in [0,r), O(1)// 大ブロックの累積和(512bit)+中ブロックの累積和(16bit)+「余り分に適切なbitmaskをかけてpopcount」int count(bool val, int r) { return val? B[r/bucket]+b[r/block]+popcount[bs[r/block]&((1<<(r%block))-1)]: r-count(1,r); }// number of val in [l,r), O(1)int count(bool val, int l, int r) { return count(val,r)-count(val,l); }// position of ith in val, 0-indexed, O(log n)// 範囲外を示していたら-1を返すint select(bool val, int i) {if(i < 0 or count(val,n) <= i) return -1;i++;int lb = 0, ub = n, md;while(ub-lb>1) {md = (lb+ub)>>1;if(count(val,md) >= i) ub = md;else lb = md;}return ub-1;}int select(bool val, int i, int l) { return select(val,i+count(val,l)); }};template<int N> char FID<N>::popcount[1<<FID<N>::block];/*****************/// Wavelet Matrix/*****************/// 長さNで、値域[0, m=2^D)の整数を管理するtemplate<class T, int N, int D> class wavelet {int n, zs[D];FID<N> dat[D];T raw_data[D+1][N] = {};T sum_data[D+1][N+1] = {};public:wavelet(int n, T seq[]) : n(n) {T l[N] = {}, r[N] = {};bool b[N] = {};memcpy(raw_data[0], seq, sizeof(T)*n);for (int d = 0; d < D; d++) {int lh = 0, rh = 0;for (int i = 0; i < n; i++) {b[i] = (raw_data[d][i]>>(D-d-1))&1;if(b[i]) r[rh++] = raw_data[d][i];else l[lh++] = raw_data[d][i];}dat[d] = FID<N>(n,b);zs[d] = lh;swap(l,raw_data[d+1]);memcpy(raw_data[d+1]+lh, r, rh*sizeof(T));}rep(d, D+1) rep(i, N) sum_data[d][i+1] = sum_data[d][i] + raw_data[d][i];}// 深さdでの列の[l, r)での累積和を求めるT getSum(int d, int l, int r) {return sum_data[d][r] - sum_data[d][l];}// rank: 区間[0,r)にあるvalの個数// O(log m)int count(T val, int l, int r) {for (int d = 0; d < D; d++) {// ここで[l, r)にxのd桁目までが全て入っていることを保証(d>0)bool b = (val>>(D-d-1))&1;l = dat[d].count(b,l)+b*zs[d];r = dat[d].count(b,r)+b*zs[d];}return r-l;}int count(T val, int r) { return count(val,0,r); }// k is 0-indexed!!!!// kth_number: 区間[l,r)でk番目に大きい数// O(log m)T kth_number(int l, int r, int k) {if(r-l <= k or k < 0) return -1;T ret = 0;for (int d = 0; d < D; d++) {int lc = dat[d].count(1,l), rc = dat[d].count(1,r);// lc - rc = [l, r)で立っている1の数if(rc-lc > k) { // 1の数にkが収まっていればl = lc+zs[d], r = rc+zs[d]; // 1側に遷移ret |= 1ULL<<(D-d-1);} else { // 0側ならばk -= rc-lc; // 1側にあった数だけkを削って次へl -= lc, r -= rc;}}return ret;}// number of elements in [l,r) in [a,b)// O(log m)int freq_dfs(int d, int l, int r, T val, T a, T b) {if(l == r) return 0;if(d == D) return (a <= val and val < b)? r-l: 0;T nv = 1ULL<<(D-d-1)|val, nnv = ((1ULL<<(D-d-1))-1)|nv;if(nnv < a or b <= val) return 0;if(a <= val and nnv < b) return r-l;int lc = dat[d].count(1,l), rc = dat[d].count(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);}int freq(int l, int r, T a, T b) { return freq_dfs(0,l,r,0,a,b); }// get sum of elements in [l,r) in [a,b)// O(log m)T sum_dfs(int d, int l, int r, T val, T a, T b) {// Wavelet Matrixの深さdで、// [l, r)が[val, nv) = [val, val+(1ll<<(D-d)))の値域を表現している時、// [a, b)の値域のものの和は?if(l == r) return 0; // valは無いので0を返すif(d == D) return (a <= val and val < b)? (r-l)*val: 0; // 深さDでは全部の値が同じなので、そのままかけて返すT nv = 1ULL<<(D-d-1)|val, nnv = ((1ULL<<(D-d-1))-1)|nv;if(nnv < a or b <= val) // どんなに1を選んでもaに満たなかったり、すでに最大を超えていたら0return 0;if (a <= val and nnv < b) // これからどう選んでも a <= [l, r) < bの場合、累積和を返すreturn getSum(d, l, r);int lc = dat[d].count(1,l), rc = dat[d].count(1,r);return sum_dfs(d+1,l-lc,r-rc,val,a,b)+ sum_dfs(d+1,lc+zs[d],rc+zs[d],nv,a,b);}T sum(int l, int r, T a, T b) { return sum_dfs(0,l,r,0,a,b); }};#define MAXN 100010#define MAXK 30int main(void) {ll n, k; cin >> n >> k; assert(1<=k&&k<=n&&n<=100000);ll a[MAXN]; rep(i, n) { cin >> a[i]; assert(1<=a[i]&&a[i]<=1e9); }wavelet<ll, MAXN, MAXK> w(n, a);ll ret = INF;rep(i, n-k+1) {ll val = w.kth_number(i, i+k, k/2);ll less_than_sum = w.sum(i, i+k, 0, val);ll more_than_sum = w.sum(i, i+k, val+1, (1ll<<MAXK)-1);ll less_than_freq = w.freq(i, i+k, 0, val);ll more_than_freq = w.freq(i, i+k, val+1, (1ll<<MAXK)-1);ll tmp = abs(more_than_sum - more_than_freq * val) + abs(less_than_sum - less_than_freq * val);chmin(ret, tmp);}cout << ret << endl;return 0;}