Submission #888938

#	Time	Username	Problem	Language	Result	Execution time	Memory
888938		JakobZorz	Holiday (IOI14_holiday)	C++17	0 / 100	5036 ms	65536 KiB

holiday

#include"holiday.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
typedef long long ll;
 
struct DS{
    multiset<ll>vals;
    ll sum=0;
    
    void add(int val){
        vals.insert(val);
        sum+=val;
    }
    
    ll get(int k){
        while(vals.size()>k){
            sum-=*vals.begin();
            vals.erase(vals.begin());
        }
        return sum;
    }
};

const int TREE_SIZE=1<<18;

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;
    }
};

int 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(get_num(node->ch1)<=k)
        return get_sum(node->ch1)+get(node->ch2,k-get_num(node->ch1));
    return get(node->ch1,k);
}
 
// 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();
    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));
    
    vector<ll>res;
    for(int d=0;d<=2*n;d++){
        // r = how far you go
        ll res1=0;
        //DS ds;
        for(int r=0;r<=d&&r<=n;r++){
            // c = how many cities you actually visit
            int c=d-r;
            //if(r)
                //ds.add(arr[r-1]);
            //cout<<"root "<<r<<endl;
            res1=max(res1,get(trees[r],c));
        }
        res.push_back(res1);
    }
    return res;
}
 
// 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<ll>res;
    for(int d=0;d<=3*n;d++){
        // r = how far you go
        ll res1=0;
        DS ds;
        for(int r=0;2*(r-1)<=d&&r<=n;r++){
            // c = how many cities you actually visit
            int c=d-2*(r-1);
            if(r)
                ds.add(arr[r-1]);
            res1=max(res1,ds.get(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));
}

Compilation message (stderr)

holiday.cpp: In member function 'll DS::get(int)':
holiday.cpp:19:26: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   19 |         while(vals.size()>k){
      |               ~~~~~~~~~~~^~

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