Submission #1065002

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065002		anango	Holiday (IOI14_holiday)	C++17	0 / 100	299 ms	27348 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> solve_for_all_d(int n, vector<int> weights) {
    //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;
    }
    
    SegmentTree st(n);
    SegmentTree st2(n);
    vector<int> firstpoint(n,-1);
    //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-1,d)<=visit(k,d)
    st.ins(0,weights[0]);
    firstpoint[0] = 2;
    int lastopt = 0;
    int lastval = 2;
    for (int k=1; k<n; k++) {
        st.ins(k,weights[k]);
        st2.ins(k-1,weights[k-1]);
        int l = k+1;
        int r = 8*n+8;
        while (l<r) {
            int m = (l+r)/2;
            int rem1 = m-k-2;
            int rem2 = m-k-1;
            //cout << l <<" " << r <<" " << rem1 <<" " << rem2 <<" " << st.get_sum_maximals(rem1) <<" " << st2.get_sum_maximals(rem2) << endl;
            if (st.get_sum_maximals(rem1)>=st2.get_sum_maximals(rem2)) {
                //visit(k,d)>=visit(k-1,d), k is better, so binsearch down
                l=l;
                r=m;
            }
            else {
                l=m+1;
                r=r;
            }
        }
        firstpoint[k] = l;
    }
    vector<int> suffmin(n,INF);
    suffmin[n-1] = firstpoint[n-1];
    for (int i=n-2; i>=0; i--) {
        suffmin[i] = min(suffmin[i+1],firstpoint[i]);
    }
    for (int i=0; i<n; i++) {
        //cout << "fsf " << i <<" " << firstpoint[i] << " " << suffmin[i] << endl;
    }
    vector<int> dans(2*n+1,0);
    int pointer = 0;
    SegmentTree st3(n);
    for (int d=0; d<=2*n; d++) {
        while (pointer<n && d>=suffmin[pointer]) {
            st3.ins(pointer,weights[pointer]);
            pointer++;
        }
        int rem = d-pointer;
        dans[d] = st3.get_sum_maximals(rem);
        //cout << d <<" " << dans[d] << " " << pointer << " " << firstpoint[pointer] <<" " << rem << endl;
    }
    
    
    return dans;
}


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[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:104: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]
  104 |     for (int i=0; i<coords.size(); i++) {
      |                   ~^~~~~~~~~~~~~~
holiday.cpp:118:9: warning: unused variable 'lastopt' [-Wunused-variable]
  118 |     int lastopt = 0;
      |         ^~~~~~~
holiday.cpp:119:9: warning: unused variable 'lastval' [-Wunused-variable]
  119 |     int lastval = 2;
      |         ^~~~~~~

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