Submission #290294

#	Time	Username	Problem	Language	Result	Execution time	Memory
290294		eohomegrownapps	Holiday (IOI14_holiday)	C++14	0 / 100	87 ms	45704 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

vector<ll> ind2coord;

struct Node{
    ll s,e,m;
    ll num = 0;
    ll sum = 0;
    ll val = 0;
    Node *l, *r;
    Node(ll _s, ll _e, bool children = true){
        s=_s;e=_e;
        //cout<<"node "<<s<<' '<<e<<endl;
        m=(s+e)/2;
        if (s==e){
            val=ind2coord[s];
            return;
        }
        if (children){
            l = new Node(s,m,true);
            r = new Node(m+1,e,true);
        }
    }

    ll query(ll k){
        if (k<0){return 0;}
        //k largest elements
        if (s==e){
            //assert(k<=num);
            return min(k,num)*val;
        }
        if (r->num>=k){
            return r->query(k);
        } else {
            return l->query(k-r->num) + r->sum;
        }
    }

    Node* update(ll ind, bool on){
        //cout<<s<<' '<<e<<endl;
        Node* ans = new Node(s,e,false);
        if (s==e){
            if (on){
                ans->num = num+1;
            } else {
                ans->num = max(0LL, num-1);
            }
            ans->sum = ans->val * ans->num;
            return ans;
        }
        if (ind<=m){
            //cout<<"left"<<endl;
            ans->l = l->update(ind,on);
            ans->r = r;
        } else {
            //cout<<"right"<<endl;
            ans->l = l;
            ans->r = r->update(ind,on);
        }
        ans->num = ans->l->num + ans->r->num;
        ans->sum = ans->l->sum + ans->r->sum;
        return ans;
    }
};

struct PersistentSet{
    vector<Node*> nodes;
    PersistentSet(){
        //cout<<"ic "<<ind2coord.size()<<endl;
        nodes.push_back(new Node(0,ind2coord.size()-1));
    }

    void insert(ll val){
        ll ind = lower_bound(ind2coord.begin(), ind2coord.end(), val)-ind2coord.begin();
        nodes.push_back(nodes.back()->update(ind,true));
    }

    ll query(ll k, ll t){
        return nodes[t]->query(k);
    }

    void clear(){
        nodes.clear();
        nodes.push_back(new Node(0,ind2coord.size()-1));
    }
};

ll rvals[200000]={0LL};
ll lvals[200000]={0LL};
ll rvals2[300000]={0LL};
ll lvals2[300000]={0LL};

PersistentSet *ps;

void dnc(ll s, ll e, ll x, ll y, ll vals[], bool thereandback){
    //cout<<s<<' '<<e<<' '<<x<<' '<<y<<endl;
    // query s,e knowing optimum lies within range x,y
    ll m = (s+e)/2;
    ll mx = -1;
    ll mxind = -1;

    for (ll v = x; v<=y; v++){
        ll test = ps->query(m-(thereandback?2*v:v),v+1);
        if (test>mx){
            mx=test;
            mxind=v;
        }
    }

    vals[m]=mx;
    if (s<m){
        dnc(s,m-1,x,mxind,vals,thereandback);
    }
    if (m<e){
        dnc(m+1,e,mxind,y,vals,thereandback);
    }
}

ll findMaxAttraction(int n, int start, int d, int attraction[]) {
    ind2coord.resize(n);
    for (ll i = 0; i<n; i++){
        ind2coord[i]=attraction[i];
    }
    sort(ind2coord.begin(),ind2coord.end());
    ind2coord.erase(unique(ind2coord.begin(),ind2coord.end()),ind2coord.end());
    //cout<<ind2coord.size()<<endl;

    ps = new PersistentSet();
    
    ps->clear();
    for (ll i = start; i<n; i++){
        ps->insert(attraction[i]);
    }
    //lvals2.resize((n-start)*4);
    dnc(0,(n-start)*4-1,0,n-1-start,lvals2,true);
    /*for (ll i : lvals2){
        cout<<i<<' ';
    }cout<<endl;*/


    ps->clear();
    for (ll i = start+1; i<n; i++){
        ps->insert(attraction[i]);
    }
    //lvals.resize((n-(start+1))*2);
    if (start+1<n){
        dnc(0,(n-(start+1))*2-1,0,n-1-(start+1),lvals,false);
    }
    /*for (ll i : lvals){
        cout<<i<<' ';
    }cout<<endl;*/


    ps->clear();
    for (ll i = start; i>=0; i--){
        ps->insert(attraction[i]);
    }
    //rvals2.resize((start+1)*4);
    dnc(0,(start+1)*4-1,0,start,rvals2,true);
    /*for (ll i : rvals2){
        cout<<i<<' ';
    }cout<<endl;*/


    ps->clear();
    for (ll i = start-1; i>=0; i--){
        ps->insert(attraction[i]);
    }
    //rvals.resize((start)*2);
    if (start-1>=0){
        dnc(0,(start)*2-1,0,start-1,rvals,false);
    }
    /*for (ll i : rvals){
        cout<<i<<' ';
    }cout<<endl;*/

    //go left then go right
    ll mx = 0;
    for (ll i = 0; i<d-1; i++){
        // i left, d right
        //if (lvals2.size()>i&&rvals.size()>d-1-i)
        mx=max(mx,lvals2[i]+rvals[d-1-i]);
        //if (rvals2.size()>i&&lvals.size()>d-1-i)
        mx=max(mx,rvals2[i]+lvals[d-i-1]);
    }
    return mx;
}

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