Submission #1114970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114970		Marco_Escandon	Rice Hub (IOI11_ricehub)	C++11	100 / 100	157 ms	20132 KiB

ricehub

#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;
}

Compilation message (stderr)

ricehub.cpp: In member function 'void st::update(ll, ll)':
ricehub.cpp:15:13: warning: statement has no effect [-Wunused-value]
   15 |         for(a; a<cad.size(); a+=(a&-a)) cad[a]+=b;
      |             ^
ricehub.cpp:15:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |         for(a; a<cad.size(); a+=(a&-a)) cad[a]+=b;
      |                ~^~~~~~~~~~~
ricehub.cpp: In member function 'll st::query(ll)':
ricehub.cpp:20:13: warning: statement has no effect [-Wunused-value]
   20 |         for(a; a>0; a-=(a&-a)) s+=cad[a];
      |             ^
ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:50:110: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'll' {aka 'long long int'} [-Wsign-compare]
   50 |         while(temp*mediana-asd.query(mapa[mediana]-1)+asd.query(mapa[mediana],300000)-(s.size()-temp)*mediana>k)
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 26 / 26
• Subtask 4: 32 / 32