Submission #1064669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064669		anango	Holiday (IOI14_holiday)	C++17	23 / 100	65 ms	9888 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
//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;
    }
};

long long findMaxAttraction(signed n, signed start, signed d, signed attraction[]) {
    
    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 attraction[i1]<attraction[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;
    }
    reverse(coords.begin(), coords.end());

    SegmentTree st(n);
    int ans = -1;
    for (int i=0; i<n; i++) {
        st.ins(i,attraction[i]);
        int rem = d-i;
        ans = max(ans,st.get_sum_maximals(rem));
    }
    return ans;
}

Compilation message (stderr)

holiday.cpp: In member function 'long long int SegmentTree::get_sum_maximals(long long int)':
holiday.cpp:78: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]
   78 |         if (current_indices.size()<k) {
      |             ~~~~~~~~~~~~~~~~~~~~~~^~
holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:103: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]
  103 |     for (int i=0; i<coords.size(); i++) {
      |                   ~^~~~~~~~~~~~~~

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