# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1009366 | Mardonbekhazratov | Rice Hub (IOI11_ricehub) | C++17 | 49 ms | 1372 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "ricehub.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
multiset<int>lept,rigt;
ll s1,s2;
void fix(){
int sz=lept.size()+rigt.size();
while(lept.size()>(sz+1)/2){
int x=*lept.rbegin();
rigt.insert(x);
lept.erase(lept.find(x));
s1-=x;
s2+=x;
}
while(rigt.size()>sz/2){
int x=*rigt.begin();
lept.insert(x);
rigt.erase(rigt.find(x));
s1+=x;
s2-=x;
}
}
void ins(int x){
if(lept.empty()){
lept.insert(x);
s1+=x;
return;
}
int mid=*lept.rbegin();
if(x>mid) rigt.insert(x),s2+=x;
else lept.insert(x),s1+=x;
fix();
}
void erase(int x){
int mid=*lept.rbegin();
if(x>mid) rigt.erase(rigt.find(x)),s2-=x;
else lept.erase(lept.find(x)),s1-=x;
fix();
}
int besthub(int R, int L, int X[], long long B){
int l=1,r=R+1;
while(r-l>1){
int mid=(l+r)/2;
bool ok=false;
for(int i=0;i<R;i++){
ins(X[i]);
if(i>=mid) erase(X[i-mid]);
if(i>=mid-1){
ll x=*lept.rbegin();
ok=ok?ok:lept.size()*x-s1+s2-rigt.size()*x<=B;
}
}
if(ok) l=mid;
else r=mid;
}
return l;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |