Submission #888968

#	Time	Username	Problem	Language	Result	Execution time	Memory
888968		JakobZorz	Holiday (IOI14_holiday)	C++17	100 / 100	507 ms	59300 KiB

holiday

#include"holiday.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
typedef long long ll;

const int TREE_SIZE=1<<17;

struct SegTree{
    int ch1,ch2;
    ll sum; // sum of active
    int num; // num of active
};

SegTree trees[2000000];
int ct;

int alloc_segtree(){
    trees[ct].sum=0;
    trees[ct].num=0;
    trees[ct].ch1=-1;
    trees[ct].ch2=-1;
    return ct++;
}

ll get_sum(int node){
    if(node==-1)
        return 0;
    return trees[node].sum;
}

int get_num(int node){
    if(node==-1)
        return 0;
    return trees[node].num;
}

int activate(int node,int idx,int val,int rl,int rr){
    int node2=alloc_segtree();
    trees[node2].ch1=trees[node].ch1;
    trees[node2].ch2=trees[node].ch2;
    
    if(rl==rr-1){
        trees[node2].sum=val;
        trees[node2].num=1;
        return node2;
    }
    int mid=(rl+rr)/2;
    if(idx<mid){
        if(trees[node2].ch1==-1)
            trees[node2].ch1=alloc_segtree();
        trees[node2].ch1=activate(trees[node2].ch1,idx,val,rl,mid);
    }else{
        if(trees[node2].ch2==-1)
            trees[node2].ch2=alloc_segtree();
        trees[node2].ch2=activate(trees[node2].ch2,idx,val,mid,rr);
    }
    trees[node2].sum=get_sum(trees[node2].ch1)+get_sum(trees[node2].ch2);
    trees[node2].num=get_num(trees[node2].ch1)+get_num(trees[node2].ch2);
    return node2;
}

// get sum of biggest k cities
ll get(int node,int k,int rl,int rr){
    k=min(k,get_num(node));
    if(k==0)
        return 0;
    if(k==get_num(node))
        return get_sum(node);
    int mid=(rl+rr)/2;
    if(get_num(trees[node].ch1)<=k)
        return get_sum(trees[node].ch1)+get(trees[node].ch2,k-get_num(trees[node].ch1),mid,rr);
    return get(trees[node].ch1,k,rl,mid);
}
 
vector<int>gen_trees(vector<int>arr){
    ct=0;
    int n=(int)arr.size();
    vector<pair<int,int>>sorted(n);
    for(int i=0;i<n;i++)
        sorted[i]={arr[i],i};
    sort(sorted.begin(),sorted.end());
    reverse(sorted.begin(),sorted.end());
    vector<int>in_sorted(n);
    for(int i=0;i<n;i++)
        in_sorted[sorted[i].second]=i;
    
    vector<int>trees;
    trees.push_back(alloc_segtree());
    for(int i=0;i<n;i++)
        trees.push_back(activate(trees.back(),in_sorted[i],sorted[in_sorted[i]].first,0,TREE_SIZE));
    return trees;
}

vector<ll>res3;
vector<int>trees3;

void gen3(int l,int r,int tl,int tr){
    int d=(l+r)/2;
    
    // r = how far you go
    ll res=0;
    int mid=0;
    for(int r=tl;r<=d&&r<=tr;r++){
        // c = how many cities you actually visit
        int c=d-r;
        ll curr=get(trees3[r],c,0,TREE_SIZE);
        if(curr>res){
            res=curr;
            mid=r;
        }
    }
    res3[d]=res;
    
    if(l<r-1){
        gen3(l,d,tl,mid);
        gen3(d,r,mid,tr);
    }
}

// if you can only walk in one direction
// return a[d] = most score if you have d days
vector<ll>get3(vector<int>arr){
    int n=(int)arr.size();
    trees3=gen_trees(arr);
    res3.resize(2*n+1);
    
    gen3(0,2*n+1,0,(int)trees3.size()-1);
    
    return res3;
}
 
vector<ll>res2;
vector<int>trees2;

void gen2(int l,int r,int tl,int tr){
    int d=(l+r)/2;
    
    // r = how far you go
    ll res=0;
    int mid=0;
    for(int r=tl;2*(r-1)<=d&&r<=tr;r++){
        // c = how many cities you actually visit
        int c=d-2*(r-1);
        ll curr=get(trees2[r],c,0,TREE_SIZE);
        if(curr>res){
            res=curr;
            mid=r;
        }
    }
    res2[d]=res;
    
    if(l<r-1){
        gen2(l,d,tl,mid);
        gen2(d,r,mid,tr);
    }
}

// if you can only walk in one direction and have to go back
// return a[d] = most score if you have d days
vector<ll>get2(vector<int>arr){
    int n=(int)arr.size();
    trees2=gen_trees(arr);
    res2.resize(3*n+1);
    
    gen2(0,3*n+1,0,(int)trees2.size()-1);
    
    return res2;
}
 
// if you first start walking to the left and then right
ll get1(vector<int>arr,int d,int s){
    int n=(int)arr.size();
    vector<int>arr1,arr2;
    for(int i=s;i>=0;i--)
        arr1.push_back(arr[i]);
    for(int i=s+1;i<n;i++)
        arr2.push_back(arr[i]);
    
    vector<ll>val1=get2(arr1),val2=get3(arr2);
    
    ll res=0;
    for(int d1=0;d1<=d;d1++){
        int d2=d-d1;
        res=max(res,val1[min(d1,(int)val1.size()-1)]+val2[min(d2,(int)val2.size()-1)]);
    }
    return res;
}
 
ll findMaxAttraction(int n,int start,int d,int attraction[]){
    vector<int>arr;
    for(int i=0;i<n;i++)
        arr.push_back(attraction[i]);
    
    ll res=get1(arr,d,start);
    reverse(arr.begin(),arr.end());
    
    return max(res,get1(arr,d,n-start-1));
}

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