結果

問題 No.738 平らな農地
ユーザー jelljell
提出日時 2018-10-02 19:28:31
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 847 ms / 2,000 ms
コード長 3,579 bytes
コンパイル時間 1,718 ms
コンパイル使用メモリ 169,080 KB
実行使用メモリ 7,308 KB
最終ジャッジ日時 2024-10-12 10:04:49
合計ジャッジ時間 29,368 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 87
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
// #include <boost/functional/hash.hpp>
// #include <boost/multiprecision/cpp_int.hpp>

#define debug 0
#define esc(ret) cout << (ret) << endl,quick_exit(0)
#define fcout(d) cout << fixed << setprecision(d)
#define repU(i,s,t) for(int i = (int)(s); i <= (int)(t); ++i)
#define repD(i,s,t) for(int i = (int)(s); i >= (int)(t); --i)
#define rep(i,n) repU(i,0,(n) - 1)
#define rep1(i,n) repU(i,1,(n))
#define all(v) begin(v),end(v)
#define vct vector
#define prique priority_queue
#define l_bnd lower_bound
#define u_bnd upper_bound
#define puf push_front
#define pub push_back
#define pof pop_front
#define pob pop_back
#define mkp make_pair
#define mkt make_tuple
#define ins insert
#define emp emplace
#define era erase
#define fir first
#define sec second
#define odd(x) ((x) & 1)
#define even(x) (!odd(x))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair<int,int> pii;
typedef pair<db,int> pdi;
typedef tuple<int,int,int> tiii;

const int dir[8][2] = { {1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,1},{-1,-1},{1,-1} };
const ll mod = 1e9 + 7;
const ll inf64 = (1LL << 62) - 1;

template <class T, class U> T qceil(T x, U y) { return x > 0 ? (x - 1) / y + 1 : x / y; }
template <class T, class U> bool parity(T x, U y) { return odd(x) ^ even(y); }
template <class T, class U> bool chmax(T &m, U x) { if(m < x) { m = x; return 1; } return 0; }
template <class T, class U> bool chmin(T &m, U x) { if(m > x) { m = x; return 1; } return 0; }
template <class T> bool cmprs(T &v) {
    T tmp = v;
    sort(all(tmp));
    tmp.erase(unique(all(tmp)),end(tmp));
    for(auto it = begin(v); it != end(v); ++it) *it = l_bnd(all(tmp),*it) - begin(tmp) + 1;
    return v.size() > tmp.size();
}

template <class Abel> struct BIT {
	int range;
	ll md;
	vector<Abel> data_;

	BIT(int size_, Abel val = 0, ll m = inf64) {
		range = size_ + 1,md = m;
		init(range,val);
	}

	void init(int n, int val) {
		data_.assign(n,val);
	}

	Abel sum(int r) {
		Abel s;
		for(s = 0; r; r -= r & -r) {
			s = (s + data_[r]) % md;
		}
		return s;
	}

	Abel sum(int l, int r) { return (sum(r) - sum(l - 1) + md) % md; }

	void add(int idx, Abel diff) {
		for(; idx < range; idx += idx & -idx) {
			data_[idx] = (data_[idx] + diff) % md;
		}
	}

	void update(int idx, Abel val) {
		int prev = sum(idx, idx);
		add(idx, val - prev);
	}

	int lower_bound(Abel obj) {
		int lower = -1;
		int upper = range;
		while (upper - lower > 1) {
			int mid = (lower + upper) / 2;
			if(sum(mid) < obj) lower = mid;
			else upper = mid;
		}
		return upper;
	}

	int upper_bound(Abel obj) {
		int lower = -1;
		int upper = range;
		while (upper - lower > 1) {
			int mid = (lower + upper) / 2;
			if(sum(mid) > obj) upper = mid;
			else lower = mid;
		}
		return upper;
	}
};

int N,K;
ll a[100010],ord[100010];
vct<pii> v;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin>>N>>K;
    BIT<ll> s(N),c(N);
    rep(i,N) cin>>a[i]; 
    rep(i,N) v.emplace_back(a[i],i);
    sort(all(v));
    rep(i,N) ord[v[i].sec] = i + 1;
    rep(i,K) s.add(ord[i],a[i]),c.add(ord[i],1);
    ll ans = inf64;
    rep(i,N + 1 - K){
        int l = c.l_bnd(K / 2);
        ll ls = s.sum(l);
        int r = c.l_bnd(K);
        ll rs = s.sum(r);
        if(even(K)){
            chmin(ans,rs - ls * 2); 
        }else{
            int m = c.l_bnd(K / 2 + 1);
            chmin(ans,rs - s.sum(m) - ls);
        }
        s.add(ord[i],-a[i]);
        c.add(ord[i],-1);
        if(i+K < N) s.add(ord[i+K],a[i+K]),c.add(ord[i+K],1);
    }
    esc(ans);
}
0