Submission #696653

#	Time	Username	Problem	Language	Result	Execution time	Memory
696653		vjudge1	Holiday (IOI14_holiday)	C++17	100 / 100	428 ms	49892 KiB

holiday

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
vector<int>vec(1,0);
struct Persistent_Segment_Tree{
    struct node{
        int l,r,val;
        long long sum;
        node(){l=r=val=sum=0;}
    };
    node t[2000000];
    int root[N],tot=0;
    void upd(int &rt,int ort,int l,int r,int X,int d){
        if(!rt)rt=++tot;
        t[rt]=t[ort];
        t[rt].val++;
        t[rt].sum+=d;
        if(l==r)return;
        int mid=(l+r)>>1;
        if(X<=mid)upd(t[rt].l=0,t[ort].l,l,mid,X,d);
        else upd(t[rt].r=0,t[ort].r,mid+1,r,X,d);
    }
    long long ask(int rtl,int rtr,int l,int r,int k){
        if(l==r)return 1ll*k*vec[l];
        int mid=(l+r)>>1;
        if(t[t[rtr].r].val-t[t[rtl].r].val>=k)return ask(t[rtl].r,t[rtr].r,mid+1,r,k);
        return ask(t[rtl].l,t[rtr].l,l,mid,k-t[t[rtr].r].val+t[t[rtl].r].val)+t[t[rtr].r].sum-t[t[rtl].r].sum;
    }
    void clear(){
        for(int i=0;i<=tot;i++)t[i]=node();
        tot=0;
    }
}tr;
long long ans;
int root[N],a[N];
int n,S,d;
void solve(int l,int r,int L,int R){
    if(l>r)return;
    int mid=(l+r)>>1;
    long long pos=L,res=0;
    for(int i=L;i<=R;++i){
        long long val=tr.ask(root[mid-1],root[i],0,vec.size(),d-(2*(i-S)+S-mid));
        if(val>=res)res=val,pos=i;
    }
    ans=max(ans,res);
    solve(l,mid-1,L,pos),solve(mid+1,r,pos,R);
}
void sl(){
    tr.clear();
    for(int i=1;i<=n;i++)tr.upd(root[i]=0,root[i-1],0,vec.size(),lower_bound(vec.begin(),vec.end(),a[i])-vec.begin(),a[i]);
    for(int i=1;i<=S;i++)ans=max(ans,tr.ask(root[i-1],root[S],0,vec.size(),d-S+i));
    solve(1,S-1,S+1,n);
}
long long findMaxAttraction(int _n,int _S,int _d,int _a[]){
    n=_n,S=_S,d=_d;
    S++;
    for(int i=1;i<=n;i++)a[i]=_a[i-1],vec.push_back(a[i]);
    sort(vec.begin(),vec.end());
    vec.erase(unique(vec.begin(),vec.end()),vec.end());
    sl(),S=n-S+1,reverse(a+1,a+n+1),sl();
    return ans;
}

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