Submission #557218

#	Time	Username	Problem	Language	Result	Execution time	Memory
557218		n0sk1ll	Rice Hub (IOI11_ricehub)	C++14	68 / 100	176 ms	37456 KiB

ricehub

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

using namespace std;
long long int typedef li;

//1-root obicnog, 2-root kurca
int val[10000007],L[10000007],R[10000007],idx=2;

void add(int p, int l, int r, int s, int x)
{
    val[p]+=x;
    if (l==r) return;
    int mid=(l+r)/2;
    if (s<=mid)
    {
        if (!L[p]) L[p]=++idx;
        add(L[p],l,mid,s,x);
    }
    else
    {
        if (!R[p]) R[p]=++idx;
        add(R[p],mid+1,r,s,x);
    }
}

int sum(int p, int l, int r, int ll, int rr)
{
    if (!p || ll>r || rr<l) return 0;
    if (ll<=l && rr>=r) return val[p];
    int mid=(l+r)/2;
    return sum(L[p],l,mid,ll,rr)+sum(R[p],mid+1,r,ll,rr);
}

int walk(int p, int l, int r, int k)
{
    if (l==r) return l;
    int mid=(l+r)/2;
    if (val[L[p]]>=k) return walk(L[p],l,mid,k);
    return walk(R[p],mid+1,r,k-val[L[p]]);
}

li balans(int m)
{
    if (m<=0) return 0;
    int p=walk(1,1,1e9,m/2);
    return ((li)sum(1,1,1e9,1,p)*p-(li)sum(2,1,1e9,1,p))+((li)sum(2,1,1e9,p,1e9)-(li)sum(1,1,1e9,p,1e9)*p);
}

int besthub(int n, int useless, int x[], li b)
{
    int l=0,r=0,mx=0;
    for (;r<n;r++)
    {
        add(1,1,1e9,x[r],1);
        add(2,1,1e9,x[r],x[r]);
        while (balans(r-l+2)>b) add(1,1,1e9,x[l],-1),add(2,1,1e9,x[l],-x[l]),l++;
        //cout<<"["<<l<<","<<r<<"] - "<<balans(r-l+2)<<endl;
        mx=max(mx,r-l+1);
    }
    return mx;
}

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