Submission #1066179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066179		anango	Holiday (IOI14_holiday)	C++17	23 / 100	1423 ms	15568 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define int long long
int INF = 1LL<<60;
//method:
//consider only going right, we'll try to compute the max obtainable with d days going to the right for each d
//now, let k be the number of cities we ever visit, and thus we get to actually see attractions of d-k cities
//we obviously visit the d-k cities with maximum attraction counts
//let visit(k,d) = max sum of visits for d with visiting the first k cities and actually opening d-k of them
//let opk[d] be the optimal number of cities to visit for d days
//note that opk[d+1]>=opk[d] (proved on paper)
//thus, for each d, there's a minimum k such that visit(k,d)<=visit(k+1,d), and from now we can use k+1 instead
//so binary search on this minimum k
//ok but we can't binary search this way round since that leads to too many insertions and erasures
//so we need to do a binary search on, for each k, the minimum d such that visit(k,d)<=visit(k+1,d)
//to do this, we need a data structure that can insert values, also query the sum of the maximum t values for any t
//this can be done with a segment tree of suffix sums with lazy propagation with coordinate compression
//since we know all the attraction values in advance 
//keep a PBDS of what values are currently in the set
const int sz = 262144;
vector<int> revcoords;
class SegmentTree {
public:
    vector<int> tree;
    int n;
    ordered_set current_indices;
    SegmentTree(int numelem) {
        tree=vector<int>(sz,0);
        n=numelem;
        //cout << "making segtree " << n << endl;
    }
    void update(int v, int l, int r, int tl, int tr, int addend) {
        
        if (l>tr || r<tl) return;
        if (l<=tl && tr<=r) {
            assert(l==r);
            tree[v]+=addend;
            return;
        }
        int m = (tl+tr)/2;
        update(2*v,l,r,tl,m,addend);
        update(2*v+1,l,r,m+1,tr,addend);
        tree[v] = tree[2*v]+tree[2*v+1];
        
    }

    int query(int v, int l, int r, int tl, int tr) {
        if (l>tr || r<tl) return 0;
        if (l<=tl && tr<=r) {
            //cout << "qend " << tl <<" " << tr <<" " << tree[v] << endl;
            return tree[v];
        }
        int m = (tl+tr)/2;
        return query(2*v,l,r,tl,m)+query(2*v+1,l,r,m+1,tr);
    }

    void ins(int index, int weight) { 
        //weight must be weights[index]
        int rc = revcoords[index];
        current_indices.insert(rc);
        //cout << "updating " << rc <<" " << weight << endl;
        update(1,rc,rc,0,131071,weight);
    }

    void era(int index, int weight) { 
        //weight must be weights[index]
        int rc = revcoords[index];
        current_indices.erase(rc);
        update(1,rc,rc,0,131071,-weight);
    }

    int get_sum_maximals(int k) {
        //(1 indexed, so k=1 means you just want max etc)
        if (current_indices.size()<k) {
            return tree[1]; //sum of everything
        }
        if (k<=0) return 0;
        int reqcid = current_indices.size(); 
        reqcid-=k;
        int req_index = *current_indices.find_by_order(reqcid);
        int ans = query(1,req_index,131071,0,131071);
        //cout << "getting " << k <<" " << current_indices.size() <<" " << reqcid <<" " << req_index << " " << ans << endl;
        return ans;
    }
};

vector<int> optimal_k;
vector<int> answers;

int state = -1; //state i means it contains 0 to i inclusive
SegmentTree st(1);

void solve(int l, int r, vector<int> &weights) {
    if (l>r) return;
    //solve for all d
    int m = (l+r)/2;
    //cout << "solving " << l <<" " << m <<" " << r << endl;
    int vleft = optimal_k[l-1];
    int vright = optimal_k[r+1];
    //find optimal_k[m], by going from vleft to vright
    while (state>vleft) {
        st.era(state,weights[state]);
        state--;
    }
    while (state<vleft) {
        state++;
        st.ins(state,weights[state]);
    }
    //state is now equal to m
    int opk = -1;
    int curbest = -1;
    for (int k=vleft; k<=vright; k++) {
        if (m-k-1<=0) continue;
        int kans = st.get_sum_maximals(m-k-1);
        //cout << "doing " << k <<" " << kans << " " << m-k-1 << " " << vleft << " " << curbest <<" " << opk << endl;
        if (kans>curbest) {
            curbest = kans;
            opk = k;
        }
        assert(state==k);
        state++;
        st.ins(state,weights[state]);
    }
    optimal_k[m] = opk;
    answers[m] = curbest;
    //cout << "solved " << l <<" " << m<<" " << r <<" " << vleft <<" "<< vright << " " << opk <<" " << curbest << endl;
    if (l<r) {
        solve(l,m-1,weights);
        solve(m+1,r,weights);
    }
    return;
    
}

vector<int> solve_for_all_d(int n, vector<int> weights) {
    st = SegmentTree(n);
    //ignore the middle itself
    revcoords=vector<int>(n,-1);
    vector<int> coords(n); iota(coords.begin(), coords.end(), (int)0);

    for (int i=0; i<n; i++) {
        //cout << weights[i] <<" ";
    }
    //cout << endl << endl;
    sort(coords.begin(), coords.end(),[&](const int i1, const int i2) {
        return weights[i1]<weights[i2];
    });
    for (int i=0; i<coords.size(); i++) {
        //revcoords is what position this index takes in the sorted list by weight
        revcoords[coords[i]] = i;
    }
    //find the optimal k for each d using divide and conquer
    //taking 0 through k
    //consider d<=2n
    optimal_k = vector<int>(2*n+1,-1);
    optimal_k[2] = 0;
    optimal_k[2*n] = n-1;
    answers=vector<int>(2*n+1,-1);
    answers[0] = answers[1] = 0;
    answers[2] = weights[0];
    answers[2*n] = accumulate(weights.begin(), weights.end(), (int)0);

    solve(3,2*n-1,weights);

    for (int i=0; i<2*n+1; i++) {
        //cout << i <<" " << optimal_k[i] <<" " << answers[i] << endl;
    }
    
    return answers;
}


long long findMaxAttraction(signed n, signed start, signed d, signed attraction[]) {
    vector<int> right;
    for (int i=start; i<n; i++) {
        right.push_back(attraction[i]);
    }
    vector<int> right_ans = solve_for_all_d(right.size(), right);
    
    return right_ans[min(2*n,d+1)];
}

Compilation message (stderr)

holiday.cpp: In member function 'long long int SegmentTree::get_sum_maximals(long long int)':
holiday.cpp:79:35: warning: comparison of integer expressions of different signedness: '__gnu_pbds::detail::bin_search_tree_set<int, __gnu_pbds::null_type, std::less<int>, __gnu_pbds::detail::tree_traits<int, __gnu_pbds::null_type, std::less<int>, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   79 |         if (current_indices.size()<k) {
      |             ~~~~~~~~~~~~~~~~~~~~~~^~
holiday.cpp: In function 'std::vector<long long int> solve_for_all_d(long long int, std::vector<long long int>)':
holiday.cpp:153:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |     for (int i=0; i<coords.size(); i++) {
      |                   ~^~~~~~~~~~~~~~

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