Submission #776176

#	Time	Username	Problem	Language	Result	Execution time	Memory
776176		alvingogo	Holiday (IOI14_holiday)	C++14	100 / 100	358 ms	51020 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define fs first
#define sc second
using namespace std;

struct PST{
    struct no{
        int lch=-1,rch=-1;
        int val=0;
        long long v2=0;
    };
    vector<no> st;
    PST(){
        st.resize(2005000);
    }
    int nw=1;
    void build(int v,int L,int R){
        if(L==R){
            return;
        }
        st[v].lch=nw;
        nw++;
        st[v].rch=nw;
        nw++;
        int m=(L+R)/2;
        build(st[v].lch,L,m);
        build(st[v].rch,m+1,R);
    }
    void update(int L,int R,int fr,int &to,int p,int t,int t2){
        to=nw;
        st[nw]=st[fr];
        st[nw].val+=t;
        st[nw].v2+=t2;
        nw++;
        if(L==R){
            return;
        }
        int m=(L+R)/2;
        if(p<=m){
            update(L,m,st[fr].lch,st[to].lch,p,t,t2);
        }
        else{
            update(m+1,R,st[fr].rch,st[to].rch,p,t,t2);
        }
    }
    long long query(int L,int R,int fr,int to,int k){
        if(L==R){
            return st[to].v2-st[fr].v2;
        }
        int sum=st[st[to].rch].val-st[st[fr].rch].val;
        int m=(L+R)/2;
        if(sum>=k){
            return query(m+1,R,st[fr].rch,st[to].rch,k);
        }
        else{
            return query(L,m,st[fr].lch,st[to].lch,k-sum)+st[st[to].rch].v2-st[st[fr].rch].v2;
        }
    }
    vector<int> root;
    int n;
    void init(vector<int> a){
        n=a.size();
        nw=1;
        root.clear();
        vector<pair<int,int> > z(n);
        for(int i=0;i<n;i++){
            z[i]={a[i],i};
        }
        sort(z.begin(),z.end());
        for(int i=0;i<n;i++){
            a[i]=lower_bound(z.begin(),z.end(),pair<int,int>(a[i],i))-z.begin();
        }
        root.resize(n+1);
        root[0]=0;
        build(0,0,n-1);
        for(int i=1;i<=n;i++){
            update(0,n-1,root[i-1],root[i],a[i-1],1,z[a[i-1]].fs);
        }
    }
    long long ask(int l,int r,int k){
        if(k<=0){
            return 0;
        }
        k=min(k,r-l+1);
        long long u=query(0,n-1,root[l],root[r+1],k);
        return u;
    }
}pst;

int n,st,k;
long long ans=0;
void dc(int l,int r,int u,int d){
    if(l>r || u>d){
        return;
    }
    pair<long long,int> p(0,0);
    int m=(l+r)/2;
    for(int i=u;i<=d;i++){
        p=max(p,{pst.ask(st-m,st+i,k-2*m-i),-i});
    }
    ans=max(ans,p.fs);
    dc(l,m-1,-p.sc,d);
    dc(m+1,r,u,-p.sc);
}
void solve(vector<int> v){
    pst.init(v);
    //dp[i][j]=pst.ask(st-i,st+j,d-2*i-j);
    int a=st,b=n-st-1;
    dc(0,a,0,b);
}
long long findMaxAttraction(int _n, int _st, int _k, int at[]) {
    n=_n;
    k=_k;
    st=_st;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        v[i]=at[i];
    }
    solve(v);
    st=_n-_st-1;
    reverse(v.begin(),v.end());
    solve(v);
    return ans;
}

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