Submission #1011491

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011491		User0069	Holiday (IOI14_holiday)	C++17	0 / 100	94 ms	58920 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,x,y,a[maxn],cur,S,opt[maxn],dp[maxn][3][2];
vector<int> v;
struct node
{
    vector<int> a;
    vector<int> pfs;
    node *l,*r;
    node()
    {
        l=r=NULL;
    }
}*root;
void cons(node* id,vector<int> v,int lval,int rval)
{
    if(v.size()==0) return;
    int mid=(lval+rval)/2;
    vector<int> s[2];
    id->a.push_back(0);
    id->pfs.push_back(0);
    for(int i:v)
    {
        int cc=id->a.back()+(a[i]>mid);
        id->a.push_back(cc);
        s[a[i]>mid].push_back(i);
        cc=id->pfs.back()+(a[i]>mid)*a[i];
        id->pfs.push_back(cc);
    }
    v.resize(0);
    if(rval==lval) return;
    id->l=new node();
    id->r=new node();
    if(s[0].size()) cons(id->l,s[0],lval,mid);
    if(s[1].size()) cons(id->r,s[1],mid+1,rval);
}
int get(node* id,int k,int l,int r,int lval,int rval)
{
    if(id==NULL||id->a.size()<=1||k<=0) return 0;
    if(lval==rval)
    {
        return min(k,(int)id->a.size())*lval;
    }
    int mid=(lval+rval)/2;
    int s1=id->a[l-1];
    int s2=id->a[r];
    if(s2-s1>k)
    {
        return get(id->r,k,s1+1,s2,mid+1,rval);
    }
    else
    {
        int cnt=id->pfs[r]-id->pfs[l-1];
        return cnt+get(id->l,k-(s2-s1),l-s1,r-s2,lval,mid);
    }
}
void dnc(int l,int r,int optl,int optr,int rev,int jump)
{
    if(l>r) return;
    int mid=(l+r)/2;
    opt[mid]=optl,dp[mid][jump][rev]=0;
    for(int i=optl;i<=optr;i++)
    {
        if(!rev)
        {
            int dd=i-S;
            int cc=get(root,mid-dd*jump,S+1,i,1,1e9);
            if(cc>=dp[mid][jump][rev]) dp[mid][jump][rev]=cc,opt[mid]=i;
        }
        if(rev)
        {
            int dd=S-i;
            int cc=get(root,mid-dd*jump,i,S-1,1,1e9);
            if(cc>=dp[mid][jump][rev]) dp[mid][jump][rev]=cc,opt[mid]=i;
        }

    }
    if(l==r) return;
    if(!rev)
    {
        dnc(l,mid-1,optl,opt[mid],rev,jump);
        dnc(mid+1,r,opt[mid],optr,rev,jump);
    }
    if(rev)
    {
        dnc(l,mid-1,opt[mid],optr,rev,jump);
        dnc(mid+1,r,optl,opt[mid],rev,jump);
    }
}
long long findMaxAttraction(int32_t n,int32_t start,int32_t d,int32_t b[])
{
    for(int i=1;i<=n;i++) v.push_back(i);
    for(int i=0;i<n;i++) a[i+1]=b[i];
    root=new node();
    
    cons(root,v,1,1e9);
    S=start;
    dnc(1,d,1,S-1,1,1);
    dnc(1,d,1,S-1,1,2);
    dnc(1,d,S+1,n,0,1);
    dnc(1,d,S+1,n,0,2);
    int ans=0;
    for(int i=0;i<=d;i++)
    {
        ans=max(dp[i][1][0]+dp[d-i][2][1],ans);
        ans=max(dp[i][1][1]+dp[d-i][2][0],ans);
        if(i<d)
        {
            ans=max(ans,dp[i][1][0]+dp[d-i-1][2][1]+a[S]);
            ans=max(ans,dp[i][1][1]+dp[d-i-1][2][0]+a[S]);
        }
    }
    return ans;
}

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