Submission #172718

#	Time	Username	Problem	Language	Result	Execution time	Memory
172718		maximath_1	Rice Hub (IOI11_ricehub)	C++11	0 / 100	6 ms	984 KiB

ricehub

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int l; vector<int>f;
void upd(int idx, int d){
	for(idx++; idx<=l; idx+=idx&(-idx)) f[idx]+=d;
}
int cnt(int idx){
	ll ans=0;
	for(; idx; idx-=idx&(-idx))
		ans+=f[idx];
	return ans;
}
int pos, res;
void find(int l, int r, long long B){
	int md=(l+r)/2;
	int howmany=cnt(r)-cnt(l-1);
	if(howmany*md<=B){
		if(howmany>res){
			pos=md; res=howmany;
		}
		return;
	}
	int lf=cnt(md)-cnt(l-1);
	int rg=cnt(r)-cnt(md-1);
	if(lf<rg) find(md+1, r, B);
	else if(lf>rg) find(l, md-1, B);
	else{
		find(l, md-1, B);
		find(md+1, r, B);
	}
	return;
}
int besthub(int R, int L, int X[], long long B){
	l=L; int mx=-1; f.resize(L+1);
	for(int i=0; i<R; i++){
		upd(X[i], 1);
		mx=max(mx, X[i]);
	}
//	for(int i=0; i<=L; i++){
//		cout<<f[i]<<" ";
//	}
//	cout<<endl;
//	return l;
	find(1, mx, B);
	return pos;
}
/*
5 20 6
1 2 10 12 14
*/

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