Submission #1073023

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073023		ProtonDecay314	Holiday (IOI14_holiday)	C++17	100 / 100	2765 ms	37524 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef short int si;
typedef vector<si> vsi;
typedef vector<vsi> vvsi;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)

/*
This segment tree stores the
cities in order of decreasing number of attractions

With this setup, we can compute the sum of the x largest elements quickly

Segtree index = kth order statistic (in decreasing array)
*/
class Tree {
    public:
        ll l, r; // SEGTREE index, NOT Node index
        Tree *lt, *rt;
        ll v, act;

        Tree(ll a_l, ll a_r): l(a_l), r(a_r), lt(nullptr), rt(nullptr), v(0ll), act(0ll) {};

        void combine() {
            act = lt->act + rt->act;
            v = lt->v * min(1ll, lt->act) + rt->v * min(1ll, rt->act);
        }

        void build(const vpll& a_ind) {
            if(l == r) {
                v = a_ind[l].fi;
                act = 0ll;
                return;
            }

            ll m = (l + r) >> 1ll;

            lt = new Tree(l, m);
            rt = new Tree(m + 1ll, r);

            lt->build(a_ind);
            rt->build(a_ind);

            combine();
        }

        void set_activation(ll i, ll nact) {
            if(l == r && r == i) {
                act = nact;
                return;
            }

            (i <= ((l + r) >> 1ll) ? lt : rt)->set_activation(i, nact);

            combine();
        }

        // We need to walk on the segment tree instead of doing a binary search
        // Binary search is too slow
        ll find_kth_active(ll x) {
            if(act < x) return -1ll;

            if(l == r) return l;

            ll m = (l + r) >> 1ll;

            if(x <= lt->act) {
                return lt->find_kth_active(x);
            } else {
                return rt->find_kth_active(x - lt->act); // lt is guaranteed to be non-null due to the l == r check
            }
        }

        ll sum_range(ll ql, ll qr) {
            if(ql > r || qr < l) return 0ll;

            if(ql == l && qr == r) return v;

            ll m = (l + r) >> 1ll;
            
            return lt->sum_range(ql, min(qr, m)) + rt->sum_range(max(ql, m + 1ll), qr);
        }

        ll sum_of_largest(ll x) {
            if(x <= 0ll) return 0ll;
            ll ind_of_last_active = find_kth_active(x);

            if(ind_of_last_active == -1ll) {
                ind_of_last_active = r;
                // cout << "OOB" << endl;
            }

            return sum_range(0ll, ind_of_last_active);
        }
};

void compute_fr(ll l, ll r, ll vl, ll vr, ll s, ll n, vll& a_inv, vll& fr, vll& maxvr, Tree& tr) {
    if(r < l) return;

    // Compute value at midpoint
    ll m = (l + r) >> 1ll;

    ll maxv = 0ll, maxi = vl;

    // Line sweep, activate values one by one
    L(i, vl, vr + 1ll) {
        tr.set_activation(a_inv[i], 1ll);
        
        // Get the sum of the largest elements
        // The segment in consideration is [s, i]
        // movement cost is i - s, so the total
        // number of visitable cities is m - i + s
        ll newv = tr.sum_of_largest(m - i + s); // ! TODO rethink
        // cout << "Anya likes peanuts, Anya hates carrots " << i << ", a_inv = " << a_inv[i] << " " << m << " " << m - i + s << " " << vr - vl << " " << newv << endl;

        if(newv > maxv) {
            maxv = newv;
            maxi = i;
        }
    }

    // Deactivate values
    L(i, vl, vr + 1ll) {
        tr.set_activation(a_inv[i], 0ll);
    }
    

    // Set fr[m] and maxvr[m] to its new value
    fr[m] = maxi;
    maxvr[m] = maxv;

    // Recurse toward the left (compute all left values)
    compute_fr(l, m - 1ll, vl, fr[m], s, n, a_inv, fr, maxvr, tr);

    // Activate everything to the left (i.e., from vl to fr[m]) (assume left has been deactivated)
    L(i, vl, fr[m]) {
        tr.set_activation(a_inv[i], 1ll);
    }

    // Recurse toward the right (compute all right values)
    compute_fr(m + 1ll, r, fr[m], vr, s, n, a_inv, fr, maxvr, tr);

    // Deactivate everything in the range vl to vr in NODE INDEX SPACE (not segtree space)
    // This is necessary to "reset" the segtree back to its original state for the next iteration
    L(i, vl, vr + 1ll) {
        tr.set_activation(a_inv[i], 0ll);
    }

    // Per level, the amount of work done is O(n log n), which should pass
}

void compute_fl(ll l, ll r, ll vl, ll vr, ll s, ll n, vll& a_inv, vll& fl, vll& maxvl, Tree& tr) {
    if(r < l) return;

    // Compute value at midpoint
    ll m = (l + r) >> 1ll;

    ll maxv = tr.sum_of_largest(m - 2 * (s - vr)), maxi = vr;

    // Line sweep, activate values one by one
    LR(i, vr - 1ll, vl - 1ll) {
        tr.set_activation(a_inv[i], 1ll);
        
        // Get the sum of the largest elements
        // The segment in consideration is [i, s)
        // movement cost is 2(s - i), so the total
        // number of visitable cities is m - 2(s - i)
        ll newv = tr.sum_of_largest(m - 2 * (s - i));
        // cout << "Anya likes peanuts, Anya hates carrots " << i << ", a_inv = " << a_inv[i] << " " << m << " " << m - 2 * (s - i) << " " << newv << endl;

        if(newv > maxv) {
            maxv = newv;
            maxi = i;
        }
    }
    

    // Set fl[m] and maxvl[m] to its new value
    fl[m] = maxi;
    maxvl[m] = maxv;

    // Deactivate values
    LR(i, vr - 1ll, vl - 1ll) {
        tr.set_activation(a_inv[i], 0ll);
    }

    // Recurse toward the left (compute all left values)
    compute_fl(l, m - 1ll, fl[m], vr, s, n, a_inv, fl, maxvl, tr);

    // Activate everything to the right (i.e., flom fl[m] to vr exclusive)
    L(i, fl[m], vr) {
        tr.set_activation(a_inv[i], 1ll);
    }

    // Recurse toward the right (compute all right values)
    compute_fl(m + 1ll, r, vl, fl[m], s, n, a_inv, fl, maxvl, tr);

    // Deactivate everything in the range vl to vr in NODE INDEX SPACE (not segtree space)
    // This is necessary to "reset" the segtree back to its original state for the next iteration
    L(i, vl, vr) {
        tr.set_activation(a_inv[i], 0ll);
    }

    // Per level, the amount of work done is O(n log n), which should pass
}

ll solve(ll n, ll s, ll d, const vll& a) {
    // Create a segment tree, sorted by decreasing values
    // Each node should have schema Node { v: ll, i: ll }
    // Here, Node.i maps from segtree ind to node ind
    // ofc, we also need a node ind to segtree ind converter
    // Which is essentially just the inverse permutation

    vpll a_ind(n, {0ll, 0ll});

    L(i, 0ll, n) {
        a_ind[i] = {a[i], i};
    }

    sort(a_ind.begin(), a_ind.end(), greater<pll>());

    Tree tr(0ll, n - 1ll);
    tr.build(a_ind);

    // a_ind :: tree ind -> [v, node ind]

    // a_ind_inv :: node ind -> tree ind

    vll a_ind_inv(n, 0ll);

    /// Invert the permutation
    L(i, 0ll, n) {
        a_ind_inv[a_ind[i].se] = i;
    }

    // First, the goal is to compute the max indices f(d) for each day d
    // This could be done using a DnC approach
    // I guess also store the maximum value for each corresponding d

    vll fr(d + 1ll, -1ll);
    vll maxvr(d + 1ll, -1ll);

    compute_fr(0ll, d, s, n - 1ll, s, n, a_ind_inv, fr, maxvr, tr);

    vll fl(d + 1ll, -1ll);
    vll maxvl(d + 1ll, -1ll);

    L(i, 0ll, n) tr.set_activation(i, 0ll); // No need for the a_inv stuff, it's just a permutation of [0, n - 1] anyways

    compute_fl(0ll, d, 0ll, s, s, n, a_ind_inv, fl, maxvl, tr);

    // In the end, we'll have two sequences fL and fR, then we'll compute
    // term index d of the max-plus convolution of fL and fR

    ll ans = 0ll;

    L(i, 0ll, d + 1ll) {
        // cout << i << " " << maxvr[i] << " " << maxvl[d - i] << endl;
        ans = max(ans, maxvr[i] + maxvl[d - i]);
    }

    return ans;
}

ll findMaxAttraction(int n, int start, int d, int attraction[]) {
    vll a(n, 0ll);

    L(i, 0ll, n) a[i] = attraction[i];

    ll ans = 0ll;

    ans = max(ans, solve((ll)n, (ll)start, (ll)d, a));

    reverse(a.begin(), a.end());

    start = n - start - 1ll;

    ans = max(ans, solve((ll)n, (ll)start, (ll)d, a));

    return ans;
}

Compilation message (stderr)

holiday.cpp: In member function 'll Tree::find_kth_active(ll)':
holiday.cpp:90:16: warning: unused variable 'm' [-Wunused-variable]
   90 |             ll m = (l + r) >> 1ll;
      |                ^

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