제출 #888956

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
888956		JakobZorz	휴가 (IOI14_holiday)	C++17	24 / 100	427 ms	65536 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 rl,rr;
    SegTree*ch1,*ch2;
    ll sum; // sum of active
    int num; // num of active
    SegTree(int l,int r){
        rl=l;
        rr=r;
        ch1=nullptr;
        ch2=nullptr;
        sum=0;
        num=0;
    }
};

ll get_sum(SegTree*node){
    if(node==nullptr)
        return 0;
    return node->sum;
}

int get_num(SegTree*node){
    if(node==nullptr)
        return 0;
    return node->num;
}

SegTree*activate(SegTree*node,int idx,int val){
    SegTree*node2=new SegTree(node->rl,node->rr);
    node2->ch1=node->ch1;
    node2->ch2=node->ch2;
    
    if(node2->rl==node2->rr-1){
        node2->sum=val;
        node2->num=1;
        return node2;
    }
    int mid=(node2->rl+node2->rr)/2;
    if(idx<mid){
        if(node2->ch1==nullptr)
            node2->ch1=new SegTree(node2->rl,mid);
        node2->ch1=activate(node2->ch1,idx,val);
    }else{
        if(node2->ch2==nullptr)
            node2->ch2=new SegTree(mid,node2->rr);
        node2->ch2=activate(node2->ch2,idx,val);
    }
    node2->sum=get_sum(node2->ch1)+get_sum(node2->ch2);
    node2->num=get_num(node2->ch1)+get_num(node2->ch2);
    return node2;
}

// get sum of biggest k cities
ll get(SegTree*node,int k){
    //cout<<node<<" "<<node->ch1<<" "<<node->ch2<<" "<<k<<endl;
    k=min(k,get_num(node));
    if(k==0)
        return 0;
    if(k==get_num(node))
        return get_sum(node);
    if(get_num(node->ch1)<=k)
        return get_sum(node->ch1)+get(node->ch2,k-get_num(node->ch1));
    return get(node->ch1,k);
}
 
vector<SegTree*>gen_trees(vector<int>arr){
    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<SegTree*>trees;
    trees.push_back(new SegTree(0,TREE_SIZE));
    for(int i=0;i<n;i++)
        trees.push_back(activate(trees.back(),in_sorted[i],sorted[in_sorted[i]].first));
    return trees;
}

vector<ll>res3;
vector<SegTree*>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);
        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);
    
    /*vector<ll>res;
    for(int d=0;d<=2*n;d++){
        // r = how far you go
        ll res1=0;
        for(int r=0;r<=d&&r<=n;r++){
            // c = how many cities you actually visit
            int c=d-r;
            res1=max(res1,get(trees[r],c));
        }
        res.push_back(res1);
    }
    return res;*/
    
    return res3;
}
 
// 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();
    vector<SegTree*>trees=gen_trees(arr);
    
    vector<ll>res;
    for(int d=0;d<=3*n;d++){
        // r = how far you go
        ll res1=0;
        for(int r=0;2*(r-1)<=d&&r<=n;r++){
            // c = how many cities you actually visit
            int c=d-2*(r-1);
            res1=max(res1,get(trees[r],c));
        }
        res.push_back(res1);
    }
    return res;
}
 
// 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);
    
    /*if(n==5){
        cout<<"val1 ";
        for(ll i:val1)
            cout<<i<<" ";
        cout<<"\n";
        
        cout<<"val2 ";
        for(ll i:val2)
            cout<<i<<" ";
        cout<<"\n";
    }*/
    
    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: 0 / 23
• Subtask 3: 17 / 17
• Subtask 4: 0 / 53