Submission #1180943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180943		AlgorithmWarrior	Holiday (IOI14_holiday)	C++20	100 / 100	210 ms	61768 KiB

holiday

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

using namespace std;

void maxself(long long& x,long long val){
    if(x<val)
        x=val;
}

int const INF=1000000000;
int const MAX=6000000;
int const NMAX=100005;
int root[NMAX];
long long ans;
int total;
int cnt[MAX],lson[MAX],rson[MAX];
long long sum[MAX];

void update(int nod,int past,int st,int dr,int poz){
    if(st==dr){
        cnt[nod]=cnt[past]+1;
        sum[nod]=sum[past]+poz;
    }
    else{
        int mij=(st+dr)/2;
        if(poz<=mij){
            lson[nod]=++total;
            rson[nod]=rson[past];
            update(lson[nod],lson[past],st,mij,poz);
        }
        else{
            lson[nod]=lson[past];
            rson[nod]=++total;
            update(rson[nod],rson[past],mij+1,dr,poz);
        }
        cnt[nod]=cnt[lson[nod]]+cnt[rson[nod]];
        sum[nod]=sum[lson[nod]]+sum[rson[nod]];
    }
}

long long get_sum(int nod1,int nod2,int st,int dr,int k){
    if(st==dr)
        return 1LL*k*st;
    int mij=(st+dr)/2;
    int dreapta=cnt[rson[nod1]]-cnt[rson[nod2]];
    if(dreapta>=k)
        return get_sum(rson[nod1],rson[nod2],mij+1,dr,k);
    return sum[rson[nod1]]-sum[rson[nod2]]+get_sum(lson[nod1],lson[nod2],st,mij,k-dreapta);
}

void dei(int l,int r,int optl,int optr,int start,int d){
    if(l>r)
        return;
    int optIndex=0;
    long long optAns=-1;
    int i;
    int mij=(l+r)/2;
    for(i=optl;i<=optr;++i){
        int drum1=start-mij;
        int drum2=i-start;
        int drum=((drum1<drum2)?2*drum1+drum2:drum1+2*drum2);
        int k=d-drum;
        long long rasp=0;
        if(k>0)
            rasp=get_sum(root[i+1],root[mij],0,INF,min(k,i-mij+1));
        if(rasp>optAns){
            optAns=rasp;
            optIndex=i;
        }
    }
    maxself(ans,optAns);
    dei(l,mij-1,optl,optIndex,start,d);
    dei(mij+1,r,optIndex,optr,start,d);
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]){
    int i;
    for(i=0;i<n;++i){
        root[i+1]=++total;
        update(root[i+1],root[i],0,INF,attraction[i]);
    }
    dei(0,start,start,n-1,start,d);
    return ans;
}

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