Submission #1012853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012853		User0069	Holiday (IOI14_holiday)	C++17	100 / 100	624 ms	27868 KiB

holiday

#include<bits/stdc++.h>
#include <holiday.h>
#define taskname ""
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define int ll
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn=1e5+3;
const int mod=1e9+7;
const int INF=1e9+1;
int n,m,k,a[maxn],b[maxn],c[maxn],cur,S,opt[3*maxn],d,dp[3*maxn][2][3];
int ST[4*maxn],sum[4*maxn];
void update(int id,int cl,int cr,int pos,int val)
{
    if(cl>pos||cr<pos) return;
    if(cl==cr)
    {
        ST[id]=1;
        sum[id]=val;
        return;
    }
    int mid=(cl+cr)/2;
    if(pos<=mid) update(2*id,cl,mid,pos,val);
    else update(2*id+1,mid+1,cr,pos,val);
    ST[id]=ST[id*2]+ST[id*2+1];
    sum[id]=sum[id*2]+sum[id*2+1];
}
int get(int id,int cl,int cr,int k)
{
    if(k<=0) return 0;
    if(ST[id]<=k) return sum[id];
    int mid=(cl+cr)/2;
    if(ST[2*id]<=k) return sum[id*2]+get(id*2+1,mid+1,cr,k-ST[id*2]);
    else return get(2*id,cl,mid,k);
}
struct seg
{
    int l,r,optl,optr;
};
void dnc(int l,int r,int rev,int jump)
{
    if(l>r) return;
    queue<seg> q;
    q.push({0,d,l,r});
    int scan=l-1;
    for(int i=1;i<=4*n;i++)
    {
        ST[i]=sum[i]=0;
    }
    while(!q.empty())
    {
        seg x=q.front();
        q.pop();
//        cout<<x.l<<" "<<x.r<<" "<<x.optl<<" "<<x.optr<<"\n";
        int mid=(x.l+x.r)/2;
        dp[mid][rev][jump]=0;
        opt[mid]=x.optl;
        if(scan>x.optl)
        {
            for(int i=1;i<=4*n;i++)
            {
                ST[i]=sum[i]=0;
            }
            scan=l-1;
        }
        while(scan<x.optl)
        {
            ++scan;
            update(1,1,n,c[scan],a[scan]);
        }
        for(int i=x.optl;i<=x.optr;i++)
        {
            update(1,1,n,c[i],a[i]);
            int d=i-l+1;
            int kk=get(1,1,n,mid-d*jump);
            if(kk>dp[mid][rev][jump])
            {
                dp[mid][rev][jump]=kk;
                opt[mid]=i;
            }
        }
        scan=x.optr;
//        cout<<mid<<" "<<dp[mid][rev][jump]<<"\n";
        if(x.l<mid) q.push({x.l,mid-1,x.optl,opt[mid]});
        if(x.r>mid) q.push({mid+1,x.r,opt[mid],x.optr});
    }
}
bool cmp(int x,int y)
{
    return a[x]>a[y];
}
long long findMaxAttraction(int32_t _n,int32_t start,int32_t _d,int32_t _a[])
{
    for(int i=0;i<_n;i++)
    {
        a[i+1]=_a[i];
        b[i+1]=i+1;
    }
    d=_d;
    n=_n;
    sort(b+1,b+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        c[b[i]]=i;
    }
//    for(int i=1;i<=n;i++)
//    {
//        cout<<c[i]<<" ";
//        update(1,1,n,c[i],a[i]);
//    }
//    cout<<"\n";
//    for(int i=1;i<=4*n;i++)
//    {
//        cout<<ST[i]<<" ";
//    }
//    cout<<"\n";
//    cout<<get(1,1,n,3)<<"\n";
    S=++start;
    dnc(S+1,n,0,1);
    dnc(S+1,n,0,2);
    for(int i=1;i<=n/2;i++)
    {
        swap(c[i],c[n+1-i]);
        swap(a[i],a[n+1-i]);
    }
    S=n+1-S;
    dnc(S+1,n,1,1);
    dnc(S+1,n,1,2);
    int ans=0;
    for(int i=0;i<=d;i++)
    {
        ans=max(dp[i][0][1]+dp[d-i][1][2],ans);
        ans=max(dp[i][1][1]+dp[d-i][0][2],ans);
        if(i<d)
        {
            ans=max(ans,dp[i][0][1]+dp[d-i-1][1][2]+a[S]);
            ans=max(ans,dp[i][1][1]+dp[d-i-1][0][2]+a[S]);
        }
    }
//    for(int i=0;i<=d;i++)
//    {
//        cout<<dp[i][1][1]<<" ";
//    }
//    cout<<"\n";
    return ans;
}
//signed main()
//{
//    if (fopen(taskname".INP","r"))
//    {
//        freopen(taskname".INP","r",stdin);
//        freopen(taskname".OUT","w",stdout);
//    }
//    Faster
//    int32_t a[]={10,2,20,40,30,1,32,15};
//    cout<<findMaxAttraction(8,4,7,a);
//}

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