Submission #861578

#	Time	Username	Problem	Language	Result	Execution time	Memory
861578		sunwukong123	Holiday (IOI14_holiday)	C++14	100 / 100	1781 ms	64052 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = -1;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi; 
map<int,int>disc;
struct node {
    int s,e,m,sum,num;
    node *l, *r;
    node(int _s, int _e){
        s=_s;e=_e;m=(s+e)/2;
        sum=num=0;
        if(s!=e){
            l=new node(s,m);
            r=new node(m+1,e);
        }
    }
    void set(int x, int nval, int value){
        //debug(x,nval,value);
        if(s==e){
            if(nval==1){
                num++;
                sum+=value;
            } else{
                num--;
                sum-=value;
            }
            return;
        }
        if(x<=m)l->set(x,nval,value);
        else r->set(x,nval,value);
        sum=l->sum+r->sum;
        num=l->num+r->num;
    }
    int kth(int x){
        if(x==0)return 0;
        if(s==e){
            //debug(sum);
            if(x)return sum;
            else return 0;
        }
        if(r->num>=x){
            return r->kth(x);
        } else {
            return r->sum + l->kth(x - r->num);
        }
    }
}*seg;
/*


*/
int A[250005];
int L[250005], R[250005];
int start;
int lidx, ridx;
void fit(int lf, int rg){
    while(ridx>rg){
        seg->set(disc[ridx],-1,A[ridx]);
        ridx--;
    }
    while(ridx<rg){
        ++ridx;
        seg->set(disc[ridx],1,A[ridx]);
    }
    while(lidx<lf){
        seg->set(disc[lidx],-1,A[lidx]);
        lidx++;
    }
    while(lidx>lf){
        --lidx;
        seg->set(disc[lidx],1,A[lidx]);
    }

    
}
void dncR(int s, int e, int optl, int optr){ 
    if(s>e)return;
    if(optl>optr)return;
    int energy=(s+e)/2; // what if we have x energy?
    pair<int,int> opt={0,optl};
    for(int i=optl;i<=optr;i++){
        fit(start,i);
        int dist=i-start;
        if(energy>dist){
            int val=seg->kth(energy-dist);
            //debug(energy,dist,i,val);
            R[energy]=max(R[energy],val);
            opt=max(opt,{val,i});
        } else{
            break;
        }
        
    }

    dncR(energy+1,e,opt.second,optr);

    dncR(s,energy-1,optl,opt.second);
    
}
void dncL(int s, int e, int optl, int optr){ 
    if(s>e)return;
    if(optl>optr)return;
    int energy=(s+e)/2; // what if we have x energy?
    pair<int,int> opt={0,-optr};
    for(int i=optr;i>=optl;i--){
        fit(i,start-1);
        int dist=start-i;
        if(energy>2*dist){
            int val=seg->kth(energy-2*dist);
            L[energy]=max(L[energy],val);
            opt=max(opt,{val,-i});
        } else{
            break;
        }
        
    }

    dncL(energy+1,e,optl,-opt.second);

    dncL(s,energy-1,-opt.second,optr);
    
}

int solve(int n, int d){
    //assume that going left cost 2 days, going right cost 1 day
    seg=new node(0,n);
    memset(L,0,sizeof L);
    memset(R,0,sizeof R);
    lidx=0,ridx=0;
    dncR(0,d,start,n);
    lidx=0,ridx=0;
    seg=new node(0,n);
    dncL(0,d,1,start-1);
    int ans=0;
    for(int i=0;i<=d;i++){
        //debug(i,L[i],R[i]);
        ans=max(ans,R[i]+L[d-i]);
    }
    return ans;
}

int findMaxAttraction(int32_t n, int32_t start, int32_t d, int32_t attraction[]) {
    ++start;
    ::start=start;
   
    for(int i=1;i<=n;i++)A[i]=attraction[i-1];
    vector<pi> vec;
    for(int i=1;i<=n;i++)vec.push_back({A[i],i});
    sort(vec.begin(),vec.end());
    for(int i=0;i<(int)vec.size();i++){
        disc[vec[i].second]=i+1;
    }
    int ans=solve(n,d);
    ::start=n-::start+1;
    reverse(A+1,A+n+1);
    vec.clear();
    for(int i=1;i<=n;i++)vec.push_back({A[i],i});
    sort(vec.begin(),vec.end());
    for(int i=0;i<(int)vec.size();i++){
        disc[vec[i].second]=i+1;
    }

    ans=max(ans,solve(n,d));
    return ans;
}

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