結果

問題 No.738 平らな農地
ユーザー jelljell
提出日時 2018-09-29 11:29:16
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,573 bytes
コンパイル時間 1,669 ms
コンパイル使用メモリ 170,324 KB
実行使用メモリ 7,420 KB
最終ジャッジ日時 2024-04-20 12:49:20
合計ジャッジ時間 26,743 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 WA -
testcase_48 WA -
testcase_49 WA -
testcase_50 WA -
testcase_51 WA -
testcase_52 WA -
testcase_53 WA -
testcase_54 WA -
testcase_55 WA -
testcase_56 WA -
testcase_57 WA -
testcase_58 WA -
testcase_59 WA -
testcase_60 WA -
testcase_61 WA -
testcase_62 WA -
testcase_63 WA -
testcase_64 WA -
testcase_65 AC 519 ms
7,016 KB
testcase_66 AC 594 ms
7,100 KB
testcase_67 WA -
testcase_68 WA -
testcase_69 WA -
testcase_70 WA -
testcase_71 AC 635 ms
7,136 KB
testcase_72 WA -
testcase_73 WA -
testcase_74 WA -
testcase_75 WA -
testcase_76 WA -
testcase_77 WA -
testcase_78 WA -
testcase_79 WA -
testcase_80 WA -
testcase_81 WA -
testcase_82 WA -
testcase_83 WA -
testcase_84 WA -
testcase_85 WA -
testcase_86 WA -
testcase_87 WA -
testcase_88 WA -
testcase_89 AC 1 ms
5,376 KB
testcase_90 AC 1 ms
5,376 KB
testcase_91 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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,md;
	vector<Abel> data_;

	BIT(int size_, Abel val = 0, int m = mod) {
		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