Submission #250065

#	Time	Username	Problem	Language	Result	Execution time	Memory
250065		mat_v	Rice Hub (IOI11_ricehub)	C++14	68 / 100	627 ms	7928 KiB

ricehub

#include "ricehub.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define N 100005

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());




int n;
int niz[N];
ll seg[4 * N][2];
ll suff[N];
ll pref[N];

void init(int node, int l, int r){
    if(l == r){
        seg[node][0] = pref[l];
        seg[node][1] = suff[l];
        return;
    }
    int mid = (l + r) / 2;
    init(node * 2, l, mid);
    init(node * 2 + 1, mid + 1, r);
    ff(j,0,1)seg[node][j] = seg[node * 2][j] + seg[node * 2 + 1][j];
}

int query(int node, int l, int r, int levo, int desno, int idx){
    if(r < levo || l > desno)return 0;
    if(l >= levo && r <= desno)return seg[node][idx];
    int mid = (l + r) / 2;
    return query(node * 2, l, mid, levo, desno, idx) + query(node * 2 + 1, mid + 1, r, levo, desno, idx);
}

int besthub(int R, int L, int X[], long long B)
{
    n = R;
    ff(i,1,n)niz[i] = X[i - 1];
    sort(niz + 1, niz + 1 + n);
    ff(i,1,n){
        pref[i] = niz[i] - niz[1];
    }
    fb(i,n,1){
        suff[i] = niz[n] - niz[i];
    }
    init(1,1,n);
    int res = 1;
    ff(i,1,n){
        int l = 0;
        int r = min(n - i, i - 1);
        while(l < r){
            int mid = (l + r + 1) / 2;
            ll prvi = query(1,1,n,i,i + mid,0) - (mid + 1) * pref[i];
            ll drugi = query(1,1,n,i - mid,i,1) - (mid + 1) * suff[i];
            if(prvi + drugi <= B){
                l = mid;
            }
            else r = mid - 1;
        }
        res = max(res, 2*l + 1);
        if(i + l >= n)continue;
        ll prvi = query(1,1,n,i,i + l + 1,0) - (l + 2) * pref[i];
        ll drugi = query(1,1,n,i - l,i,1) - (l + 1) * suff[i];
        if(prvi + drugi <= B)res = max(res, 2*l + 2);
    }
    return res;
}

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