oj.uz

Submission #172718

# Submission time Handle Problem Language Result Execution time Memory
172718 2020-01-02T12:52:14 Z maximath_1 Rice Hub (IOI11_ricehub) C++11
0 / 100
 6 ms 984 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 984 KB Output isn't correct
2 Halted 0 ms 0 KB -