# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1114969 | Marco_Escandon | Rice Hub (IOI11_ricehub) | C++17 | 0 ms | 0 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 <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
struct st{
vector<ll> cad;
void update(ll a, ll b)
{
for(a; a<cad.size(); a+=(a&-a)) cad[a]+=b;
}
ll query(ll a)
{
ll s=0;
for(a; a>0; a-=(a&-a)) s+=cad[a];
return s;
}
ll query(ll a, ll b) {return query(b)-query(a-1);}
st(ll n){ cad.resize(n+5);}
}asd(300000);
int besthub(int R, int L, int X[], long long B)
{
ll n=R,k=B,c=1;
ordered_set s;
ll cad[n];
vector<ll>asdf;
map<ll,ll> mapa;
for(int i=0; i<n; i++)
{
cad[i]=X[i]
asdf.push_back(cad[i]);
}
sort(asdf.begin(),asdf.end());
for(auto i:asdf){if(mapa[i]==0){mapa[i]=c++;}}
ll z=0;
ll bs=0;
for(int i=0; i<n; i++)
{
s.insert(cad[i]);
asd.update(mapa[cad[i]],cad[i]);
ll mediana = *s.find_by_order((s.size()-1)/2);
ll temp=s.order_of_key(mediana);
while(temp*mediana-asd.query(mapa[mediana]-1)+asd.query(mapa[mediana],300000)-(s.size()-temp)*mediana>k)
{
s.erase(s.find_by_order(s.order_of_key(cad[z])));
asd.update(mapa[cad[z]],-cad[z]);
z++;
mediana = *s.find_by_order((s.size()-1)/2);
temp=s.order_of_key(mediana);
}
//cerr<<temp*mediana-asd.query(mapa[mediana]-1)+asd.query(mapa[mediana],300000)-(s.size()-temp)*mediana<<" ";
//cerr<<z<<" "<<i<<"\n";
bs=max(bs,(ll)s.size());
}
return (int)bs;
}