#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
int* a;
int n,l; long long b, T[2][100010], S[2];
vector<int> vx;
multiset<int> lt,rt;
void update(int t, int p, long long x) {
for(int i=p+1;i<=vx.size();i+=i&-i) T[t][i]+=x;
S[t]+=x;
}
long long query(int t, int p) {
long long ret=0;
for(int i=p+1;i>0;i-=i&-i) ret+=T[t][i];
return ret;
}
void Add(int x) {
int lo=-2e9,hi=2e9;
if(!lt.empty()) lo=*lt.rbegin();
if(!rt.empty()) hi=*rt.begin();
if(x<=lo){
if(lt.size()==rt.size()+1) {
rt.insert(lo);
lt.erase(lt.find(lo));
}
lt.insert(x);
} else if(x<hi) {
if(lt.size()==rt.size()+1) rt.insert(x);
else lt.insert(x);
} else {
if(lt.size()==rt.size()) {
lt.insert(hi);
rt.erase(rt.find(hi));
}
rt.insert(x);
}
update(0,x,vx[x]);
update(1,x,1);
}
void Remove(int x) {
if(lt.size()==rt.size()) {
if(rt.find(x)==rt.end()) {
lt.insert(*rt.begin());
rt.erase(rt.begin());
lt.erase(lt.find(x));
} else rt.erase(rt.find(x));
} else {
if(lt.find(x)==lt.end()) {
rt.insert(*lt.rbegin());
lt.erase(lt.find(*lt.rbegin()));
rt.erase(rt.find(x));
} else lt.erase(lt.find(x));
}
update(0,x,-vx[x]);
update(1,x,-1);
}
long long Calc(int x) {
long long s1=query(0,x), s2=S[0]-s1;
long long c1=query(1,x), c2=S[1]-c1;
return vx[x]*(c1-c2)-s1+s2;
}
bool f(int x) {
lt.clear(); rt.clear();
int i;
for(i=0;i<x;i++) {
Add(a[i]);
}
long long r=Calc(*lt.rbegin());
for(i=x;i<n;i++) {
Add(a[i]);
Remove(a[i-x]);
r=min(r,Calc(*lt.rbegin()));
}
return r<=b;
}
int besthub(int R, int L, int X[], long long B)
{
vx.clear();
n=R,l=L,b=B,a=X;
for(int i=0;i<R;i++) vx.push_back(X[i]);
sort(vx.begin(),vx.end());
vx.erase(unique(vx.begin(),vx.end()),vx.end());
for(int i=0;i<R;i++) a[i]=lower_bound(vx.begin(),vx.end(),a[i])-vx.begin();
int lo=0,hi=R;
while(lo<hi){
int mid=(lo+hi+1)/2;
if(f(mid)) lo=mid;
else hi=mid-1;
}
return lo;
}
Compilation message
ricehub.cpp: In function 'void update(int, int, long long int)':
ricehub.cpp:9:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=p+1;i<=vx.size();i+=i&-i) T[t][i]+=x;
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
86 ms |
1400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
