#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 best_hub(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);
// }
Compilation message
/usr/bin/ld: /tmp/cctusmI7.o: in function `main':
grader.cpp:(.text.startup+0xae): undefined reference to `besthub(int, int, int*, long long)'
collect2: error: ld returned 1 exit status
