Submission #1008760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008760		tosivanmak	Holiday (IOI14_holiday)	C++17	100 / 100	454 ms	43996 KiB

holiday

#include<bits/stdc++.h>
using namespace std;
#define ll long long
 
ll val[100005],ver[100005];
vector<ll>disc;
ll n;
ll find(ll k){
    return lower_bound(disc.begin(),disc.end(),k)-disc.begin();
}
struct PSEG{
    ll sum[2200005];
    int cnt[2200005],lc[2200005],rc[2200005];
    ll assign=1;
    ll build(ll l, ll r){
        if(l==r){
            assign++;
        }
        else{
            ll mid=(l+r)>>1;
            build(l,mid);
            ll le=assign-1;
            build(mid+1,r);
            ll ri=assign-1;
            lc[assign]=le,rc[assign]=ri;
            // cout<<l<<" "<<r<<" "<<assign<<" "<<lc[assign]<<" "<<rc[assign]<<'\n';
            assign++;
        }
        if(l==0&&r==n-1)return assign-1;
        return 0;
    }
    ll upd(ll ul, ll l, ll r, ll valsum, ll valcnt, ll id){
        if(l==r){
            ll cur=assign;assign++;
            sum[cur]=sum[id]+valsum;
            cnt[cur]=cnt[id]+valcnt;
            lc[cur]=0,rc[cur]=0;
        }
        else{
            ll mid=(l+r)>>1;
            if(ul<=mid){
                upd(ul,l,mid,valsum,valcnt,lc[id]);
                ll cur=assign++;
                sum[cur]=sum[id]+valsum,cnt[cur]=cnt[id]+valcnt;
                lc[cur]=cur-1,rc[cur]=rc[id];
            }
            else{
                upd(ul,mid+1,r,valsum,valcnt,rc[id]);
                ll cur=assign;assign++;
                sum[cur]=sum[id]+valsum,cnt[cur]=cnt[id]+valcnt;
                lc[cur]=lc[id],rc[cur]=cur-1;
            }
        }
        if(l==0&&r==n-1){
            return assign-1;
        }
        return 0;
    }
    void bs(ll& totsum, ll id1, ll id2, ll l, ll r, ll k){
        if(l==r){
            totsum+=(min((ll)k,(ll)cnt[id1]-cnt[id2])*val[l]);
            // cout<<totsum<<'\n';
            return;
        }
        ll mid=(l+r)>>1;
        if(cnt[rc[id1]]-cnt[rc[id2]]>=k){
            bs(totsum,rc[id1],rc[id2],mid+1,r,k);
        }
        else{
            totsum+=sum[rc[id1]]-sum[rc[id2]];
            bs(totsum,lc[id1],lc[id2],l,mid,k-(cnt[rc[id1]]-cnt[rc[id2]]));
        }
    }
    void clear(){
        for(int i=1;i<=2000000;i++){
            sum[i]=0,cnt[i]=0,lc[i]=0,rc[i]=0;
        }
        assign=1;
    }
}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,ver[to+1],ver[from],0,n-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]);
    }
    // return 0;
    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];
    ver[0]=st.build(0,n-1);
    for(int i=0;i<_n;i++){
        ver[i+1]=st.upd(find(att[i]),0,n-1,att[i],1,ver[i]);
    }
    // return 0;
    starting=start,day=d;
    find_bst(0,start,0,_n-1);
    st.clear();
    reverse(att.begin(),att.end());
    ver[0]=st.build(0,n-1);
    starting=_n-starting-1;
    for(int i=0;i<_n;i++){
        ver[i+1]=st.upd(find(att[i]),0,n-1,att[i],1,ver[i]);
    }
    find_bst(0,starting,0,_n-1);
    return ans;
}
// int main() {
//     int n, start, d;
//     int attraction[100000];
//     int i, n_s;
//     n_s = scanf("%d %d %d", &n, &start, &d);
//     for (i = 0 ; i < n; ++i) {
// 	n_s = scanf("%d", &attraction[i]);
//     }
//     printf("%lld\n", findMaxAttraction(n, start, d,  attraction));
//     return 0;
// }

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