Submission #1008731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008731		tosivanmak	Holiday (IOI14_holiday)	C++17	47 / 100	151 ms	65536 KiB

holiday

#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll val[100005];
vector<ll>disc;
ll n;
ll find(ll k){
    return lower_bound(disc.begin(),disc.end(),k)-disc.begin();
}
struct PSEG{
  vector<vector<ll> >sum,cnt,lc,rc;
    void init(ll n){
        sum.resize(4*n+5),cnt.resize(4*n+5),lc.resize(4*n+5),rc.resize(4*n+5);
        for(int i=0;i<4*n+5;i++){
            sum[i].push_back(0),cnt[i].push_back(0),lc[i].push_back(0),rc[i].push_back(0);
        }
    }
    void upd(ll ver, ll ul, ll l, ll r, ll valsum, ll valcnt, ll id){
        if(l==r){
            sum[id].push_back(sum[id][ver]+valsum);
            cnt[id].push_back(cnt[id][ver]+valcnt);
            lc[id].push_back(0),rc[id].push_back(0);
        }
        else{
            ll mid=(l+r)>>1;
            if(ul<=mid){
                sum[id].push_back(sum[id][ver]+valsum),cnt[id].push_back(cnt[id][ver]+valcnt);
                upd(lc[id][ver],ul,l,mid,valsum,valcnt,id*2);
                lc[id].push_back(lc[id*2].size()-1),rc[id].push_back(rc[id][ver]);
            }
            else{
                sum[id].push_back(sum[id][ver]+valsum),cnt[id].push_back(cnt[id][ver]+valcnt);
                upd(rc[id][ver],ul,mid+1,r,valsum,valcnt,id*2+1);
                lc[id].push_back(lc[id][ver]),rc[id].push_back(rc[id*2+1].size()-1);
            }
        }
    }
    void bs(ll& totsum, ll ver1, ll ver2, ll l, ll r, ll id, ll k){
        if(l==r){
            totsum+=min(k,cnt[id][ver1])*val[l];
            // cout<<totsum<<'\n';
            return;
        }
        ll mid=(l+r)>>1;
        if(cnt[id*2+1][rc[id][ver1]]-cnt[id*2+1][rc[id][ver2]]>=k){
            bs(totsum,rc[id][ver1],rc[id][ver2],mid+1,r,id*2+1,k);
        }
        else{
            totsum+=sum[id*2+1][rc[id][ver1]]-sum[id*2+1][rc[id][ver2]];
            bs(totsum,lc[id][ver1],lc[id][ver2],l,mid,id*2,k-(cnt[id*2+1][rc[id][ver1]]-cnt[id*2+1][rc[id][ver2]]));
        }
    }
    void clear(){sum.clear(),cnt.clear(),lc.clear(),rc.clear();}
}st;
int starting,day;
ll ans=0;
vector<ll>att;
ll cost(ll from, ll to, ll k){
    // cout<<from<<" "<<to<<" "<<k<<'\n';
    if(from>to)return -1e18;
    if(k<0)return -1e18;
    ll extra=to-from;
    if(k<=extra)return -1e18;
    k-=extra;
    ll ans=0;
    // cout<<to+1<<' '<<from<<" "<<k<<'\n';
    st.bs(ans,to+1,from,0,n-1,1,k);
    return ans;
}
void find_bst(ll l, ll r, ll optl, ll optr){
    if(l>r)return;
    ll mid=(l+r)>>1;
    ll bstid=optl,bst=cost(mid,optl,day-(abs(mid-starting)));
    ll kk=day-abs(mid-starting);
    for(int i=optl+1;i<=optr;i++){
        if(cost(mid,i,kk)>bst){
            bst=cost(mid,i,kk),bstid=i;
        }
    }
    ans=max(ans,bst);
    find_bst(l,mid-1,optl,bstid),find_bst(mid+1,r,bstid,optr);
}
ll findMaxAttraction(int _n, int start, int d, int attraction[]){
    n=_n;
    for(int i=0;i<_n;i++){
        att.push_back(attraction[i]);
    }
    for(int i=0;i<_n;i++){
        disc.push_back(att[i]);
    }
    sort(disc.begin(),disc.end());disc.erase(unique(disc.begin(),disc.end()),disc.end());
    n=disc.size();
    for(int i=0;i<n;i++)val[i]=disc[i];
    st.init(n);
    for(int i=0;i<_n;i++){
        st.upd(i,find(att[i]),0,n-1,att[i],1,1);
    }
    starting=start,day=d;
    find_bst(0,start,0,_n-1);
    st.clear();
    reverse(att.begin(),att.end());
    st.init(n);
    starting=_n-starting-1;
    for(int i=0;i<_n;i++){
        st.upd(i,find(att[i]),0,n-1,att[i],1,1);
    }
    find_bst(0,starting,0,_n-1);
    return ans;
}

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