Submission #1015245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015245		amirhoseinfar1385	Holiday (IOI14_holiday)	C++17	100 / 100	229 ms	8380 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10,lg=19,kaf=(1<<lg);
long long all[maxn],n,st,k,allind[maxn];
long long mainres=0;
struct segment{
    long long seg[(1<<(lg+1))];
    void upd(long long i,long long w){
        i+=kaf;
        while(i>0){
            seg[i]+=w;
            i>>=1;
        }
        return ;
    }
    long long pors(long long i,long long l,long long r,long long tl,long long tr){
        if(l>r||l>tr||r<tl||tl>tr){
            return 0;
        }
        if(l>=tl&&r<=tr){
            return seg[i];
        }
        long long m=(l+r)>>1;
        return pors((i<<1),l,m,tl,tr)+pors((i<<1)^1,m+1,r,tl,tr);
    }
    long long porsakh(long long i,long long l,long long r,long long w){
        if(l>r||seg[i]<w){
            return -1;
        }
        if(l==r){
            return l;
        }
        long long m=(l+r)>>1;
        if(seg[(i<<1)^1]>=w){
            return porsakh((i<<1)^1,m+1,r,w);
        }
        return porsakh((i<<1),l,m,w-seg[(i<<1)^1]);
    }
}seg1,seg2;

void ins(int l,int r,int w){
    for(int i=l;i<=r;i++){
        seg1.upd(allind[i],w*all[i]);
        seg2.upd(allind[i],w);
    }
}

void solve(long long l,long long r,long long tl,long long tr){
    if(l>r){
        return ;
    }
    long long mid=(l+r)>>1,opt=tl,mx=-1;
    ins(max(l,tr+1),mid,1);
    for(long long i=tr;i>=tl;i--){
        seg2.upd(allind[i],1);
        seg1.upd(allind[i],all[i]);
        long long ted=k-(mid-i+min(mid-st,st-i));
        long long z=seg2.porsakh(1,0,kaf-1,ted);
        long long fake=seg1.pors(1,0,kaf-1,z,n+1);
        if(fake>mx){
            mx=fake;
            opt=i;
        }
    }
    ins(max(l,tr+1),mid,-1);
    ins(tl,tr,-1);
    mainres=max(mainres,mx);

    ins(opt+1,min(tr,l-1),1);   

    solve(l,mid-1,tl,opt);

    ins(opt+1,min(tr,l-1),-1);   

    ins(max(tr+1,l),mid,1);

    solve(mid+1,r,opt,tr);
    ins(max(tr+1,l),mid,-1);
}

long long findMaxAttraction(int N,int start,int d,int attraction[]) {
    n=N;
    st=start;
    k=d;
    st++;
    vector<pair<long long ,long long>>comper;
    for(long long i=1;i<=n;i++){
        all[i]=attraction[i-1];
        comper.push_back(make_pair(all[i],i));
    }
    sort(comper.begin(),comper.end());
    comper.resize(unique(comper.begin(),comper.end())-comper.begin());
    for(long long i=1;i<=n;i++){
        allind[i]=lower_bound(comper.begin(),comper.end(),make_pair(all[i],i))-comper.begin();
    }
    solve(st,n,1,st);
    return mainres;
}

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