Submission #500565

#	Time	Username	Problem	Language	Result	Execution time	Memory
500565		beaconmc	Rice Hub (IOI11_ricehub)	C++17	100 / 100	113 ms	7984 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>


typedef long long ll;
#define FOR(i, x, y) for(ll i=x; i<y; i++)

using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
  
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>

ordered_set sustree;
ll  median, newmed;
ll rsum,lsum;

ll insert(ll a){
    if (sustree.size() == 0) median = a;
    else median = *sustree.find_by_order((sustree.size()-1)/2);

    if (a <= median && sustree.size()%2==1) lsum += a,lsum -= median, rsum += median;
    else if (a<=median) lsum += a;

    else{
        sustree.insert(a);
        median = *sustree.find_by_order((sustree.size()-1)/2);
        if (sustree.size()%2 == 0) rsum += a;
        else lsum += median, rsum -= median, rsum += a;
        goto lol;
    }
    sustree.insert(a);
    lol:
    median = *sustree.find_by_order((sustree.size()-1)/2);
    if (sustree.size() %2 == 1) return rsum - lsum + median;
    else return rsum - lsum;
}


ll remove(ll a){
    median = *sustree.find_by_order((sustree.size()-1)/2);
    if (sustree.size()%2==1){
        if (a<=median) lsum -= a;
        else lsum -= median, rsum -= a, rsum += median;
    } 
    else{
        sustree.erase(sustree.find_by_order(sustree.order_of_key(a)));
        median = *sustree.find_by_order((sustree.size()-1)/2);
        if (a<=median) lsum -= a, lsum += median, rsum -= median;
        else rsum -= a;
        goto lmao;
    }
    sustree.erase(sustree.find_by_order(sustree.order_of_key(a)));
    lmao:
    median = *sustree.find_by_order((sustree.size()-1)/2);
    if (sustree.size() %2 == 1) return rsum - lsum + median;
    else return rsum - lsum;
}


int besthub(int R, int L, int X[], ll B){
    ll maxi = 0;
    ll lo = 0;
    ll hi = 0;
    while (lo<=hi && hi<R){
        if (insert(X[hi]) <= B){
            hi++;
        }else{
            remove(X[hi]);
            remove(X[lo]);
            lo++;
        }
        maxi = max(maxi, hi-lo);
    }
    return maxi;
}
/*int main(){
    int R,L,B;
    cin >> R >> L >> B;
    int X[R];
    FOR(i, 0, R){
        cin >> X[i];
    }
    cout << besthub(R, L, X, B);
}*/

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