oj.uz

Submission #873581

# Submission time Handle Problem Language Result Execution time Memory
873581 2023-11-15T10:22:10 Z HuyQuang_re_Zero Holiday (IOI14_holiday) C++14
100 / 100
 1331 ms 54100 KB 
#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,x=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];
        x|=(j<<i);
    }
    return res+t*x;
}





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()
{
    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];
    r=new trie();
    L=1; R=0;
    solve();
    change(1,0);

    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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 1196 KB Output is correct
2 Correct 238 ms 1116 KB Output is correct
3 Correct 68 ms 1192 KB Output is correct
4 Correct 72 ms 1116 KB Output is correct
5 Correct 221 ms 1116 KB Output is correct
6 Correct 18 ms 944 KB Output is correct
7 Correct 112 ms 1016 KB Output is correct
8 Correct 144 ms 1064 KB Output is correct
9 Correct 15 ms 1116 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3420 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 5 ms 3420 KB Output is correct
4 Correct 17 ms 3420 KB Output is correct
5 Correct 15 ms 3164 KB Output is correct
6 Correct 4 ms 1628 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 4 ms 860 KB Output is correct
9 Correct 3 ms 604 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 1116 KB Output is correct
2 Correct 238 ms 54100 KB Output is correct
3 Correct 738 ms 26972 KB Output is correct
4 Correct 18 ms 2908 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 4 ms 848 KB Output is correct
8 Correct 1331 ms 20440 KB Output is correct
9 Correct 1305 ms 20680 KB Output is correct