Submission #832807

#	Time	Username	Problem	Language	Result	Execution time	Memory
832807		ttamx	Holiday (IOI14_holiday)	C++14	24 / 100	63 ms	65536 KiB

holiday

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

using namespace std;

typedef long long ll;

const int N=1e5+5;
const ll inf=1e18;

int n,d,st;
int a[N];
vector<pair<int,int>> vec;
int mp[N];
ll dp[4][2*N];

struct persist{
    struct node;
    typedef node* pnode;
    struct node{
        ll val;
        int freq;
        pnode l,r;
        node(ll val,int freq):val(val),freq(freq),l(nullptr),r(nullptr){}
    };
    pnode rt[N];
    void build(int l,int r,pnode &t){
        t=new node(0,0);
        if(l==r)return;
        int m=(l+r)/2;
        build(l,m,t->l);
        build(m+1,r,t->r);
    }
    void build(int t){
        build(1,n,rt[t]);
    }
    void update(int l,int r,pnode &t,pnode k,int x,ll v){
        t=new node(*k);
        t->val+=v;
        t->freq++;
        if(l==r)return;
        int m=(l+r)/2;
        if(x<=m)update(l,m,t->l,k->l,x,v);
        else update(m+1,r,t->r,k->r,x,v);
    }
    void update(int k,int t,int x,ll v){
        update(1,n,rt[t],rt[k],x,v);
    }
    ll query(int l,int r,pnode t,int k){
        if(l==r)return k>0?t->val:0;
        int m=(l+r)/2;
        int freq=t->r->freq;
        if(freq<k)return query(l,m,t->l,k-freq)+t->r->val;
        return query(m+1,r,t->r,k);
    }
    ll query(int t,int k){
        return query(1,n,rt[t],k);
    }
}s;

void solve(int l,int r,int optl,int optr,int id,int mul){
    if(l>r)return;
    int mid=(l+r)/2;
    pair<ll,int> best(-inf,-1);
    for(int i=optl;i<=optr;i++)best=max(best,{s.query(i,mid-mul*abs(i-st)),i});
    int opt;
    tie(dp[id][mid],opt)=best;
    if(id%2==0){
        solve(l,mid-1,optl,opt,id,mul);
        solve(mid+1,r,opt,optr,id,mul);
    }else{
        solve(l,mid-1,opt,optr,id,mul);
        solve(mid+1,r,optl,opt,id,mul);
    }
}

ll findMaxAttraction(int _n,int start,int _d,int _a[]) {
    n=_n,d=_d,st=start+1;
    for(int i=1;i<=n;i++){
        a[i]=_a[i-1];
        vec.emplace_back(a[i],i);
    }
    sort(vec.begin(),vec.end());
    for(int i=0;i<n;i++)mp[vec[i].second]=i+1;
    s.build(st);
    for(int i=st+1;i<=n;i++)s.update(i-1,i,mp[i],a[i]);
    for(int i=st-1;i>=1;i--)s.update(i+1,i,mp[i],a[i]);
    solve(1,d,st,n,0,2);
    solve(1,d,1,st,1,2);
    s.update(st,st,mp[st],a[st]);
    for(int i=st+1;i<=n;i++)s.update(i-1,i,mp[i],a[i]);
    for(int i=st-1;i>=1;i--)s.update(i+1,i,mp[i],a[i]);
    solve(1,d,st,n,2,1);
    solve(1,d,1,st,3,1);
    ll ans=0;
    for(int i=0;i<=d;i++){
        ans=max(ans,dp[0][i]+dp[3][d-i]);
        ans=max(ans,dp[1][i]+dp[2][d-i]);
    }
    return ans;
}

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