Submission #873558

#	Time	Username	Problem	Language	Result	Execution time	Memory
873558		HuyQuang_re_Zero	Holiday (IOI14_holiday)	C++14	7 / 100	69 ms	6236 KiB

holiday

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#include "holiday.h"
using namespace std;
struct trie
{
    int cnt;
    ll sum;
    trie *c[2];
} *r;
void add(int x)
{
    trie *u=r;
    u->cnt++;
    u->sum+=x;
    for(int i=29;i>=0;i--)
    {
        if(u->c[BIT(x,i)]==NULL) u->c[BIT(x,i)]=new trie();
        u=u->c[BIT(x,i)];
        u->cnt++;
        u->sum+=x;
    }
}
void del(int x)
{
    trie *u=r;
    u->cnt--;
    u->sum-=x;
    for(int i=29;i>=0;i--)
    {
        u=u->c[BIT(x,i)];
        u->cnt--;
        u->sum-=x;
    }
}
ll get(int t)
{
    trie *u=r;
    if(u->cnt<t) return u->sum;
    ll res=0;
    for(int i=29;i>=0;i--)
    {
        int j;
        for(j=1;j>=0;j--)
        {
            if(u->c[j]==NULL) continue;
            if(t>u->c[j]->cnt) t-=(u->c[j]->cnt),res+=u->c[j]->sum;
            else break;
        }
        u=u->c[j];
    }
    return res+t*(u->sum);
}





int a[100005],L,R,i,start,m,n;
ll res;
void change(int u,int v)
{
    while(R<v) add(a[++R]);
    while(L>u) add(a[--L]);
    while(R>v) del(a[R--]);
    while(L<u) del(a[L++]);
}
void Divide(int l,int r,int u,int v)
{
    if(l>r) return ;
    int mid=(l+r)>>1;
    ll ma=0,pos=0;
    for(int i=u;i<=v;i++)
    {
        change(mid,i);
        ll k=get(max(0,m-2*(start-mid)-(i-start)));
        if(ma<k) ma=k,pos=i;
    }
    res=max(res,ma);
    Divide(l,mid-1,u,pos);
    Divide(mid+1,r,pos,v);
}
void solve()
{
    r=new trie();
    L=1; R=0;
    Divide(1,start,start,n);
}
ll findMaxAttraction(int _n,int _start,int _m,int _a[])
{
    n=_n; m=_m;
    start=_start+1;
    for(i=n;i>=1;i--) a[i]=_a[i-1];
    solve();
    start=n-start+1;
    for(i=1;i<=n/2;i++) swap(a[i],a[n-i+1]);
    solve();
    return res;
}

/*
int main()
{
    freopen("holiday.inp","r",stdin);
    freopen("holiday.out","w",stdout);
    cin>>n>>start>>m;
    for(i=0;i<n;i++) cin>>a[i];
    cout<<findMaxAttraction(n,start,m,a);
}
*/

• Subtask 1: 7 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53