Submission #591265

#	Time	Username	Problem	Language	Result	Execution time	Memory
591265		Drew_	Holiday (IOI14_holiday)	C++17	100 / 100	1543 ms	11200 KiB

holiday

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

#define pb push_back
#define mp make_pair
#define f1 first
#define s2 second

using ll = long long;

struct Segtree
{
    int n;
    pair<ll, int> st[1 << 18];
    
    Segtree() {}
    Segtree(int n_) : n(n_) { fill(st, st + (1 << 18), mp(0, 0)); }

    inline void modify(int p, ll val)
    {
        const auto _modify = [&](const auto &self, int node, int l, int r) -> void
        {
            if (l > p || r < p)
                return;
            if (l == r)
            {
                st[node] = { val, val > 0 };
                return;
            }
            int mid = (l + r) >> 1;
            self(self, node << 1, l, mid);
            self(self, node << 1 | 1, mid+1, r);

            st[node].f1 = st[node << 1].f1 + st[node << 1 | 1].f1;
            st[node].s2 = st[node << 1].s2 + st[node << 1 | 1].s2;
        };
        _modify(_modify, 1, 0, n-1);
    }

    inline ll query(int x)
    {
        const auto _query = [&](const auto &self, int node, int l, int r) -> ll
        {
            if (x <= 0)
                return 0;
            if (l == r)
                return st[node].f1;

            int mid = (l + r) >> 1;
            if (x <= st[node << 1].s2)
                return self(self, node << 1, l, mid);
            x -= st[node << 1].s2;
            return st[node << 1].f1 + self(self, node << 1 | 1, mid+1, r);
        };
        return _query(_query, 1, 0, n-1);
    }
};

vector<ll> solve(vector<int> item, int D, int C)
{
    if (item.empty())
        return vector<ll>(D+1, 0);

    int N = (int)item.size();
    Segtree st(N);
    vector<ll> res(D+1);

    vector<int> id(N);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&](const int &x, const int &y){
        return item[x] > item[y];
    });

    {
        vector<int> tmp(N);
        for (int i = 0; i < N; ++i)
            tmp[id[i]] = i;
        id = tmp;
    }

    const auto dnc = [&](const auto &self, int l, int r, int optL, int optR) -> void
    {
        if (l > r)
            return;
        int mid = (l + r) >> 1;

        ll optVal = -1;
        int optIdx = -1;

        // costs `C * i` stamina to get to that spot
        for (int i = optL; i <= optR && C*i <= mid; ++i)
        {
            st.modify(id[i], item[i]);
            ll val = st.query(mid - C*i);

            if (val > optVal)
            {
                optVal = val;
                optIdx = i;
            }
        }
        res[mid] = optVal;


        for (int i = optL; i <= min(mid, optR); ++i)
            st.modify(id[i], 0);
        self(self, l, mid-1, optL, optIdx);

        for (int i = optL; i < optIdx; ++i)
            st.modify(id[i], item[i]);
        self(self, mid+1, r, optIdx, optR);
    };
    dnc(dnc, 0, D, 0, N-1);

    return res;
}

ll findMaxAttraction(int n, int start, int d, int attraction[])
{
    vector<int> vl = { 0 }, vr;
    for (int i = start-1; i >= 0; --i)
        vl.pb(attraction[i]);
    for (int i = start; i < n; ++i)
        vr.pb(attraction[i]);

    ll res = 0;
    for (int rep = 0; rep < 2; ++rep)
    {
        vector<ll> L = solve(vl, d, 1);
        vector<ll> R = solve(vr, d, 2);

        for (int i = 0; i <= d; ++i)
            res = max(res, L[i] + R[d - i]);

        vl.swap(vr);
    }
    
    return res;
}

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