Submission #857547

#	Time	Username	Problem	Language	Result	Execution time	Memory
857547		abcvuitunggio	Holiday (IOI14_holiday)	C++17	100 / 100	1332 ms	12220 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
int n,s,d,a[100001],idx[100001],pos[100001];
long long p[250001][2];
pair <long long, int> st[400001];
void update(int node, int l, int r, int i){
    if (l>i||r<i||l>r)
        return;
    if (l==r){
        st[node].second^=1;
        st[node].first=st[node].second*a[i];
        return;
    }
    int mid=(l+r)>>1;
    update(node<<1,l,mid,i);
    update(node<<1|1,mid+1,r,i);
    st[node]={st[node<<1].first+st[node<<1|1].first,st[node<<1].second+st[node<<1|1].second};
}
long long get(int node, int l, int r, int x){
    if (st[node].second<=x)
        return st[node].first;
    int mid=(l+r)>>1;
    return (st[node<<1|1].second<x?get(node<<1,l,mid,x-st[node<<1|1].second)+st[node<<1|1].first:get(node<<1|1,mid+1,r,x));
}
void dnc(int l, int r, int optl, int optr, int idx){
    if (l>r||optl>optr)
        return;
    int mid=(l+r)>>1;
    pair <long long, int> tmp={0,-1e9};
    for (int i=optl;i<=min(s+mid/(idx+1),optr);i++){
        update(1,0,n-1,pos[i]);
        tmp=max(tmp,make_pair(get(1,0,n-1,mid-(i-s)*(idx+1)),-i));
    }
    p[mid][idx]=tmp.first;
    int opt=-tmp.second;
    for (int i=opt;i<=min(s+mid/(idx+1),optr);i++)
        update(1,0,n-1,pos[i]);
    dnc(mid+1,r,opt,optr,idx);
    for (int i=optl;i<opt;i++)
        update(1,0,n-1,pos[i]);
    dnc(l,mid-1,optl,opt,idx);
}
long long solve(){
    for (int i=0;i<n;i++)
        idx[i]=i;
    for (int i=0;i<=d;i++)
        p[i][0]=p[i][1]=0;
    sort(idx,idx+n,[](int i, int j){return make_pair(a[i],i)<make_pair(a[j],j);});
    sort(a,a+n);
    for (int i=0;i<n;i++)
        pos[idx[i]]=i;
    if (s<n-1){
        s++;
        dnc(0,d,s,n-1,0);
        s--;
    }
    reverse(pos,pos+n);
    s=n-1-s;
    dnc(0,d,s,n-1,1);
    long long res=0;
    for (int i=0;i<d;i++)
        res=max(res,p[i][0]+p[d-i-1][1]);
    return res;
}
long long findMaxAttraction(int N, int start, int D, int attraction[]){
    n=N;
    s=start;
    d=D;
    for (int i=0;i<n;i++)
        a[i]=attraction[i];
    long long res=solve();
    for (int i=0;i<n;i++)
        a[i]=attraction[n-i-1];
    return max(res,solve());
}

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