제출 #787064

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
787064		allin27x	쌀 창고 (IOI11_ricehub)	C++17	100 / 100	217 ms	13032 KiB

ricehub

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
int val[(int) 1e5+4];
unordered_map<int, int> key;
 
vector<int> a;
int n;

struct SGT{
	vector<int> t;
	int n;
	int ofs;
	SGT(vector<int> ar, bool indexed = false){
		n = ar.size();
		ofs = indexed?(1ll<<(int)(ceil(log2(n+1)))) : n;
		t.resize(2*ofs, 0);
		for (int i=0; i<n; i++) t[ofs+i] = ar[i];
		for (int i=ofs-1; i>0; i--) t[i] = t[i<<1] + t[i<<1|1];
 
	}
	void update(int p, int inc){
		for (t[p+=ofs]+=inc; p>1; p>>=1) t[p>>1] = t[p] + t[p^1];
	}
	int query(int l, int r){
		int res = 0;
		for (l+=ofs,r+=ofs+1; l<r; l>>=1, r>>=1){
			if (l&1) res += t[l++];
			if (r&1) res += t[--r];
		}
		return res;
	}
	int median(){
		int p=1;
		int m = (t[1]+1)/2;
		for (; p<ofs;) 
			if (t[p<<1]<m) m-=t[p<<1], p =p<<1|1;
			else p = p<<1;
		return p-ofs;
	}
};
 
int calc(SGT &freq, SGT &sum){
	int m = freq.median();
	return val[m]*freq.query(0,m)-sum.query(0,m) + sum.query(m,sum.n-1) - val[m]*freq.query(m, freq.n-1);
}
 
int check(int k, int B){
	vector<int> b (n, 0);
	SGT freq = SGT(b, 1);
	SGT sum  = SGT(b, 0);
	for (int i=0; i<k; i++) freq.update(key[a[i]], 1), sum.update(key[a[i]], a[i]);	
	if (calc(freq, sum)<=B) return 1;
	for (int r = k; r<n; r++){
		freq.update(key[a[r]],1); freq.update(key[a[r-k]], -1);
		sum.update(key[a[r]], a[r]); sum.update(key[a[r-k]], -a[r-k]);
		if (calc(freq, sum)<=B) return 1;
	}
	return 0;
}

signed besthub(signed R, signed L, signed X[], int B){	
	n = R;
	int ind = 0, last = -1;
	for (int i=0; i<n; i++){
		if (X[i] == last) continue;
		last = X[i];
		val[ind] = X[i];
		key[X[i]] = ind++;
	}
	a.resize(R);
	for (int i=0; i<R; i++) a[i] = X[i];

	int l = 0, r = R;
	while (l<r){
		int m = (l+r+1)/2;
		if (check(m,B)){
			l = m;
		} else {
			r = m - 1;
		}
	}
	return l;
}

// signed main(){
// 	signed r= 5; signed l = 20; 
// 	signed x[] = {1,2,10,12,14};
// 	int b = 6;
// 	cout<<best_hub(r, l , x, b);
// }

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 26 / 26
• Subtask 4: 32 / 32