#288984 (C++11) No.738 平らな農地

提出ソース

結果

問題	No.738 平らな農地
ユーザー	jell
提出日時	2018-10-02 19:28:31
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	841 ms / 2,000 ms
コード長	3,579 bytes
コンパイル時間	1,880 ms
コンパイル使用メモリ	169,308 KB
実行使用メモリ	7,408 KB
最終ジャッジ日時	2024-04-20 14:31:02
合計ジャッジ時間	29,191 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
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	1 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	8 ms 5,376 KB
testcase_06	AC	10 ms 5,376 KB
testcase_07	AC	7 ms 5,376 KB
testcase_08	AC	5 ms 5,376 KB
testcase_09	AC	3 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	4 ms 5,376 KB
testcase_12	AC	3 ms 5,376 KB
testcase_13	AC	8 ms 5,376 KB
testcase_14	AC	3 ms 5,376 KB
testcase_15	AC	470 ms 6,856 KB
testcase_16	AC	365 ms 6,940 KB
testcase_17	AC	453 ms 7,000 KB
testcase_18	AC	662 ms 6,828 KB
testcase_19	AC	593 ms 7,264 KB
testcase_20	AC	517 ms 7,016 KB
testcase_21	AC	841 ms 7,144 KB
testcase_22	AC	545 ms 7,028 KB
testcase_23	AC	508 ms 7,200 KB
testcase_24	AC	714 ms 7,032 KB
testcase_25	AC	4 ms 5,376 KB
testcase_26	AC	4 ms 5,376 KB
testcase_27	AC	3 ms 5,376 KB
testcase_28	AC	3 ms 5,376 KB
testcase_29	AC	3 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	2 ms 5,376 KB
testcase_37	AC	3 ms 5,376 KB
testcase_38	AC	4 ms 5,376 KB
testcase_39	AC	4 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	421 ms 7,308 KB
testcase_46	AC	326 ms 6,976 KB
testcase_47	AC	461 ms 7,112 KB
testcase_48	AC	264 ms 7,024 KB
testcase_49	AC	257 ms 7,000 KB
testcase_50	AC	274 ms 7,100 KB
testcase_51	AC	523 ms 7,120 KB
testcase_52	AC	415 ms 7,000 KB
testcase_53	AC	455 ms 7,048 KB
testcase_54	AC	492 ms 7,004 KB
testcase_55	AC	539 ms 7,120 KB
testcase_56	AC	361 ms 7,084 KB
testcase_57	AC	296 ms 6,964 KB
testcase_58	AC	446 ms 7,076 KB
testcase_59	AC	295 ms 7,312 KB
testcase_60	AC	271 ms 7,288 KB
testcase_61	AC	342 ms 7,140 KB
testcase_62	AC	390 ms 6,976 KB
testcase_63	AC	455 ms 7,308 KB
testcase_64	AC	497 ms 7,148 KB
testcase_65	AC	567 ms 7,004 KB
testcase_66	AC	644 ms 7,100 KB
testcase_67	AC	392 ms 6,976 KB
testcase_68	AC	280 ms 7,044 KB
testcase_69	AC	460 ms 7,048 KB
testcase_70	AC	342 ms 7,248 KB
testcase_71	AC	685 ms 7,136 KB
testcase_72	AC	377 ms 6,976 KB
testcase_73	AC	315 ms 7,028 KB
testcase_74	AC	446 ms 6,956 KB
testcase_75	AC	408 ms 6,844 KB
testcase_76	AC	342 ms 7,052 KB
testcase_77	AC	441 ms 6,832 KB
testcase_78	AC	670 ms 7,408 KB
testcase_79	AC	696 ms 7,296 KB
testcase_80	AC	470 ms 7,056 KB
testcase_81	AC	593 ms 7,004 KB
testcase_82	AC	491 ms 7,100 KB
testcase_83	AC	621 ms 7,316 KB
testcase_84	AC	600 ms 7,168 KB
testcase_85	AC	516 ms 7,284 KB
testcase_86	AC	662 ms 6,964 KB
testcase_87	AC	50 ms 7,072 KB
testcase_88	AC	48 ms 6,852 KB
testcase_89	AC	2 ms 5,376 KB
testcase_90	AC	2 ms 5,376 KB
testcase_91	AC	1 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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);
}

yukicoder

結果

テストケース

ソースコード