Submission #751141

#	Time	Username	Problem	Language	Result	Execution time	Memory
751141		tranxuanbach	Rice Hub (IOI11_ricehub)	C++17	100 / 100	59 ms	5968 KiB

ricehub

#include "ricehub.h"

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

const int N = 1e5 + 5;

int n;
int a[N];

multiset <int> mtslo, mtshi;
ll sumlo, sumhi;

int median(){
    return mtslo.empty() ? INT_MAX : *mtslo.rbegin();
}

ll cal_dist(){
    int m = median();
    return sumhi - (ll)m * isz(mtshi) + (ll)m * isz(mtslo) - sumlo;
}

void balance(){
    while (isz(mtslo) > isz(mtshi) + 1){
        int x = *mtslo.rbegin();
        mtslo.erase(mtslo.find(x));
        sumlo -= x;
        mtshi.insert(x);
        sumhi += x;
    }
    while (isz(mtslo) < isz(mtshi)){
        int x = *mtshi.begin();
        mtshi.erase(mtshi.find(x));
        sumhi -= x;
        mtslo.insert(x);
        sumlo += x;
    }
}

void insert(int x){
    if (x <= median()){
        mtslo.insert(x);
        sumlo += x;
    }
    else{
        mtshi.insert(x);
        sumhi += x;
    }
    balance();
}

void erase(int x){
    if (mtslo.find(x) != mtslo.end()){
        mtslo.erase(mtslo.find(x));
        sumlo -= x;
    }
    else{
        mtshi.erase(mtshi.find(x));
        sumhi -= x;
    }
    balance();
}

int besthub(int _n, int l, int _a[], ll val){
    n = _n;
    For(i, 0, n){
        a[i] = _a[i];
    }

    int ans = 0;
    int r = -1;
    For(l, 0, n){
        while (r + 1 < n){
            r++;
            insert(a[r]);
            if (cal_dist() > val){
                erase(a[r]);
                r--;
                break;
            }
        }
        ans = max(ans, r - l + 1);
        erase(a[l]);
    }
    return ans;
}

/*
==================================================+
INPUT                                             |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

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