結果
問題 | No.738 平らな農地 |
ユーザー | ゆにぽけ |
提出日時 | 2024-03-06 06:34:44 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 69 ms / 2,000 ms |
コード長 | 5,078 bytes |
コンパイル時間 | 1,584 ms |
コンパイル使用メモリ | 140,120 KB |
実行使用メモリ | 10,064 KB |
最終ジャッジ日時 | 2024-09-29 18:13:34 |
合計ジャッジ時間 | 7,827 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,820 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 2 ms
6,816 KB |
testcase_03 | AC | 2 ms
6,820 KB |
testcase_04 | AC | 2 ms
6,820 KB |
testcase_05 | AC | 3 ms
6,816 KB |
testcase_06 | AC | 3 ms
6,820 KB |
testcase_07 | AC | 3 ms
6,816 KB |
testcase_08 | AC | 2 ms
6,820 KB |
testcase_09 | AC | 2 ms
6,816 KB |
testcase_10 | AC | 2 ms
6,820 KB |
testcase_11 | AC | 2 ms
6,816 KB |
testcase_12 | AC | 2 ms
6,820 KB |
testcase_13 | AC | 2 ms
6,816 KB |
testcase_14 | AC | 2 ms
6,820 KB |
testcase_15 | AC | 38 ms
7,296 KB |
testcase_16 | AC | 39 ms
7,296 KB |
testcase_17 | AC | 41 ms
7,168 KB |
testcase_18 | AC | 41 ms
7,040 KB |
testcase_19 | AC | 48 ms
7,296 KB |
testcase_20 | AC | 39 ms
7,296 KB |
testcase_21 | AC | 46 ms
7,424 KB |
testcase_22 | AC | 40 ms
7,296 KB |
testcase_23 | AC | 45 ms
7,424 KB |
testcase_24 | AC | 45 ms
7,296 KB |
testcase_25 | AC | 2 ms
6,816 KB |
testcase_26 | AC | 2 ms
6,816 KB |
testcase_27 | AC | 2 ms
6,816 KB |
testcase_28 | AC | 2 ms
6,816 KB |
testcase_29 | AC | 2 ms
6,816 KB |
testcase_30 | AC | 2 ms
6,816 KB |
testcase_31 | AC | 2 ms
6,820 KB |
testcase_32 | AC | 2 ms
6,816 KB |
testcase_33 | AC | 1 ms
6,824 KB |
testcase_34 | AC | 2 ms
6,820 KB |
testcase_35 | AC | 2 ms
6,820 KB |
testcase_36 | AC | 2 ms
6,820 KB |
testcase_37 | AC | 2 ms
6,816 KB |
testcase_38 | AC | 2 ms
6,820 KB |
testcase_39 | AC | 3 ms
6,816 KB |
testcase_40 | AC | 2 ms
6,816 KB |
testcase_41 | AC | 2 ms
6,816 KB |
testcase_42 | AC | 2 ms
6,816 KB |
testcase_43 | AC | 3 ms
6,816 KB |
testcase_44 | AC | 2 ms
6,816 KB |
testcase_45 | AC | 43 ms
9,628 KB |
testcase_46 | AC | 40 ms
7,296 KB |
testcase_47 | AC | 41 ms
9,416 KB |
testcase_48 | AC | 38 ms
7,424 KB |
testcase_49 | AC | 37 ms
7,424 KB |
testcase_50 | AC | 41 ms
9,496 KB |
testcase_51 | AC | 43 ms
9,468 KB |
testcase_52 | AC | 39 ms
7,296 KB |
testcase_53 | AC | 42 ms
9,424 KB |
testcase_54 | AC | 43 ms
9,508 KB |
testcase_55 | AC | 42 ms
9,488 KB |
testcase_56 | AC | 42 ms
9,460 KB |
testcase_57 | AC | 37 ms
7,424 KB |
testcase_58 | AC | 41 ms
9,424 KB |
testcase_59 | AC | 41 ms
9,452 KB |
testcase_60 | AC | 41 ms
9,528 KB |
testcase_61 | AC | 41 ms
9,556 KB |
testcase_62 | AC | 39 ms
7,296 KB |
testcase_63 | AC | 44 ms
9,600 KB |
testcase_64 | AC | 42 ms
9,508 KB |
testcase_65 | AC | 55 ms
7,296 KB |
testcase_66 | AC | 58 ms
7,296 KB |
testcase_67 | AC | 33 ms
9,824 KB |
testcase_68 | AC | 33 ms
9,796 KB |
testcase_69 | AC | 41 ms
9,904 KB |
testcase_70 | AC | 37 ms
9,984 KB |
testcase_71 | AC | 10 ms
6,820 KB |
testcase_72 | AC | 16 ms
6,816 KB |
testcase_73 | AC | 15 ms
6,816 KB |
testcase_74 | AC | 17 ms
6,820 KB |
testcase_75 | AC | 45 ms
9,796 KB |
testcase_76 | AC | 41 ms
9,852 KB |
testcase_77 | AC | 48 ms
9,788 KB |
testcase_78 | AC | 52 ms
9,932 KB |
testcase_79 | AC | 44 ms
10,064 KB |
testcase_80 | AC | 40 ms
9,908 KB |
testcase_81 | AC | 43 ms
9,800 KB |
testcase_82 | AC | 43 ms
10,012 KB |
testcase_83 | AC | 15 ms
6,816 KB |
testcase_84 | AC | 16 ms
6,820 KB |
testcase_85 | AC | 69 ms
10,008 KB |
testcase_86 | AC | 60 ms
9,616 KB |
testcase_87 | AC | 34 ms
9,844 KB |
testcase_88 | AC | 33 ms
9,752 KB |
testcase_89 | AC | 2 ms
6,820 KB |
testcase_90 | AC | 2 ms
6,820 KB |
testcase_91 | AC | 2 ms
6,816 KB |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <array> #include <iterator> #include <string> #include <cctype> #include <cstring> #include <cstdlib> #include <cassert> #include <cmath> #include <ctime> #include <iomanip> #include <numeric> #include <stack> #include <queue> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <bitset> #include <random> #include <utility> #include <functional> using namespace std; template<class T,T (*op)(T,T),T (*e)()> struct segtree { private: int size,N; vector<T> node; public: segtree(int N = 0) : segtree(vector<T>(N,e())) {} segtree(const vector<T> &V) { N = (int)V.size(); size = 1; while(size < N) { size <<= 1; } node.assign(2 * size,e()); for(int i = 0;i < N;i++) { node[i + size] = V[i]; } for(int i = size - 1;i >= 1;i--) { node[i] = op(node[2 * i],node[2 * i + 1]); } } void replace(int pos,T x) { func_update(pos,x,[](T u,T v){return u = v;}); } void add(int pos,T x) { func_update(pos,x,[](T u,T v){return u + v;}); } void func_update(int pos,T x) { func_update(pos,x,op); } void func_update(int pos,T x,T (*func)(T,T)) { assert(0 <= pos && pos < N); pos += size; node[pos] = func(node[pos],x); while(pos >> 1) { pos >>= 1; node[pos] = op(node[2 * pos],node[2 * pos + 1]); } } T operator[](int pos) { assert(0 <= pos && pos < N); return node[pos + size]; } int get_log() { int res = 0; while(1 << res < size) { res++; } assert((1 << res) == size); return res; } vector<vector<T>> tree_list() { vector<vector<T>> res; int log = get_log(); res.reserve(log + 1); for(int i = 0;i <= log;i++) { int L = 1 << log,R = L << 1; vector<T> cur(node.begin() + L,node.begin() + R); res.push_back(cur); } return res; } //suppose that class T has ostream &operator<< void print(int k) { assert(0 <= k && k <= get_log()); int L = 1 << k,R = L << 1; for(int i = L;i < R;i++) { cerr << node[i] << (i + 1 == R ? "\n":" "); } } void print() { int log = get_log(); for(int k = 0;k <= log;k++) { int L = 1 << k,R = L << 1; const string unit((1 << (log - k)) - 1,' '); for(int i = L;i < R;i++) { if(i == L) { cerr << unit; } cerr << node[i].cnt; if(i + 1 < R) { cerr << unit << unit << ' '; } else { cerr << unit; } } cerr << "\n"; } } T prod(int l,int r) { assert(0 <= l && l <= r && r <= N); T L = e(),R = e(); l += size,r += size; while(l < r) { if(l & 1) { L = op(L,node[l++]); } if(r & 1) { R = op(node[--r],R); } l >>= 1,r >>= 1; } return op(L,R); } T prod() { return node[1]; } template<class F> int max_right(int l,F f) { assert(0 <= l && l <= N); assert(f(e())); if(l == N) { return N; } l += size; T val = e(); do { while(!(l & 1)) { l >>= 1; } if(!f(op(val,node[l]))) { while(l < size) { l <<= 1; if(f(op(val,node[l]))) { val = op(val,node[l++]); } } return l - size; } val = op(val,node[l++]); } while((l & -l) != l); return N; } template<class F> int min_left(int r,F f) { assert(0 <= r && r <= N); assert(f(e())); if(r == 0) { return 0; } r += size; T val = e(); do { r--; while(r > 1 && (r & 1)) { r >>= 1; } if(!f(op(node[r],val))) { while(r < size) { r <<= 1; r++; if(f(op(node[r],val))) { val = op(node[r--],val); } } return r + 1 - size; } val = op(node[r],val); } while((r & -r) != r); return 0; } }; struct dat { long long sum; int cnt; }; dat op(dat a,dat b) { a.sum += b.sum; a.cnt += b.cnt; return a; } dat e() { return dat{0,0}; } void Main() { int N,K; cin >> N >> K; vector<int> A(N); for(int i = 0;i < N;i++) { cin >> A[i]; } vector<int> comp(A.begin(),A.end()); sort(comp.begin(),comp.end()); comp.erase(unique(comp.begin(),comp.end()),comp.end()); vector<dat> init(comp.size()); vector<int> id(N); for(int i = 0;i < N;i++) { id[i] = lower_bound(comp.begin(),comp.end(),A[i]) - comp.begin(); if(i < K) { init[id[i]] = op(init[id[i]],dat{A[i],1}); } } segtree<dat,op,e> seg(init); long long ans = (long long)9e18; for(int i = K;i <= N;i++) { { int mr = seg.max_right(0,[&K](dat x) {return x.cnt < (K + 1) / 2;}); dat L = seg.prod(0,mr); dat all = seg.prod(); assert(all.cnt == K); dat x = seg[mr]; long long lsum = L.sum; long long allsum = all.sum; lsum += (long long) (K / 2 - L.cnt) * comp[mr]; long long cur = allsum - lsum - lsum; if(K & 1) { cur -= comp[mr]; } ans = min(ans,cur); /* seg.print(); */ } if(i < N) { int out = id[i - K],in = id[i]; seg.func_update(out,dat{-A[i - K],-1}); seg.func_update(in,dat{A[i],1}); } } cout << ans << "\n"; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int tt = 1; /* cin >> tt; */ while(tt--) Main(); }