제출 #1093002

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1093002		shivansh0809	휴가 (IOI14_holiday)	C++17	24 / 100	85 ms	65536 KiB

holiday

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

const int N = 100'002;

struct Vertex
{
    Vertex *l, *r;
    int sum;
    long long k_sum;
    Vertex(int val) : l(nullptr), r(nullptr), sum(val), k_sum(0) {}
    Vertex(int val, long long k_sum) : l(nullptr), r(nullptr), sum(val), k_sum(k_sum) {}
    Vertex(Vertex *l, Vertex *r) : l(l), r(r), sum(0), k_sum(0)
    {
        if (l)
            sum += l->sum, k_sum += l->k_sum;
        if (r)
            sum += r->sum, k_sum += r->k_sum;
    }
};

Vertex *roots[N];

struct PersistentSegTree
{ // find_kth returns the kth smallest element in the array in [l, r)

    map<int, pair<int, int>> compress;
    int n;

    PersistentSegTree(int v[], int n) : n(n)
    {
        int tl = 0, tr = n;
        pair<int, int> sort_v[n];
        for (int i = 0; i < n; i++)
            sort_v[i] = {v[i], i};
        sort(sort_v, sort_v + n, greater<pair<int, int>>());
        int idx[n];
        for (int i = 0; i < n; i++)
            compress[i] = sort_v[i], idx[sort_v[i].second] = i;
        roots[0] = build(tl, tr);
        for (int i = 0; i < n; i++)
            roots[i + 1] = update(roots[i], tl, tr, idx[i]);
    }

    Vertex *build(int tl, int tr)
    {
        if (tl == tr)
            return new Vertex(0, 0);
        int tm = (tl + tr) / 2;
        return new Vertex(build(tl, tm), build(tm + 1, tr));
    }
    Vertex *update(Vertex *v, int tl, int tr, int pos)
    {
        if (tl == tr)
            return new Vertex(v->sum + 1, v->k_sum + compress[pos].first);
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            return new Vertex(update(v->l, tl, tm, pos), v->r);
        else
            return new Vertex(v->l, update(v->r, tm + 1, tr, pos));
    }

    long long find_kth(Vertex *vl, Vertex *vr, int tl, int tr, int k)
    {
        if (tl == tr)
            return vr->k_sum - vl->k_sum;
        int tm = (tl + tr) / 2;
        int left_count = vr->l->sum - vl->l->sum;
        if (left_count >= k)
            return find_kth(vl->l, vr->l, tl, tm, k);
        return vr->l->k_sum - vl->l->k_sum + find_kth(vl->r, vr->r, tm + 1, tr, k - left_count);
    }

    long long find_kth(int l, int r, int k)
    {
        return find_kth(roots[l], roots[r], 0, n, k);
    }
};

long long int findMaxAttraction(int n, int start, int d, int attraction[])
{
    long long int ans = 0;
    PersistentSegTree pst(attraction, n);
    function<long long(int, int)> C1 = [&](int k, int mid) -> long long
    {
        int days_rem = d - (mid - k + start - k);
        if (days_rem <= 0)
            return 0;
        return pst.find_kth(k, mid + 1, days_rem);
        // return mid - k;
    };
    function<long long(int, int)> C2 = [&](int mid, int k) -> long long
    {
        int days_rem = d - (k - mid + k - start);
        if (days_rem <= 0)
            return 0;
        return pst.find_kth(mid, k + 1, days_rem);
        // return k - mid;
    };

    // function<void(int, int, int, int)> dncg = [&](int l, int r, int optl, int optr)
    // {
    //     if (l > r)
    //         return;

    //     int mid = (l + r) >> 1;
    //     pair<long long, int> best = {-1, -1};

    //     for (int k = optl; k <= min(mid, optr); k++)
    //         best = max(best, {C1(k, mid), k});

    //     // debug(dp, best, ndp);
    //     // debug(ans, best, mid);
    //     ans = max(best.first, ans);
    //     int opt = best.second;

    //     dncg(l, mid - 1, optl, opt);
    //     dncg(mid + 1, r, opt, optr);
    // };
    // function<void(int, int, int, int)> dncs = [&](int l, int r, int optl, int optr)
    // {
    //     if (l > r)
    //         return;

    //     int mid = (l + r) >> 1;
    //     pair<long long, int> best = {-1, -1};

    //     for (int k = optr; k >= max(mid, optl); k--)
    //         best = max(best, {C2(mid, k), k});

    //     // debug(dp, best, ndp);
    //     // debug(ans, best, mid);
    //     ans = max(best.first, ans);
    //     int opt = best.second;

    //     dncs(l, mid - 1, optl, opt);
    //     dncs(mid + 1, r, opt, optr);
    // };
    if (d == 0)
        return 0;
    ans = attraction[start];
    vector<array<int, 4>> dncg, dncs;
    dncg.push_back({start + 1, n - 1, 0, start});
    dncs.push_back({0, start - 1, start, n - 1});
    while (!dncg.empty())
    {
        auto [l, r, optl, optr] = dncg.back();
        dncg.pop_back();
        if (l > r)
            continue;

        int mid = (l + r) >> 1;
        pair<long long, int> best = {-1, -1};

        for (int k = optl; k <= min(mid, optr); k++)
            best = max(best, {C1(k, mid), k});

        // debug(dp, best, ndp);
        // debug(ans, best, mid);
        ans = max(best.first, ans);
        int opt = best.second;

        dncg.push_back({mid + 1, r, opt, optr});
        dncg.push_back({l, mid - 1, optl, opt});
    }
    while (!dncs.empty())
    {
        auto [l, r, optl, optr] = dncs.back();
        dncs.pop_back();
        if (l > r)
            continue;

        int mid = (l + r) >> 1;
        pair<long long, int> best = {-1, -1};

        for (int k = optr; k >= max(mid, optl); k--)
            best = max(best, {C2(mid, k), k});

        // debug(dp, best, ndp);
        // debug(ans, best, mid);
        ans = max(best.first, ans);
        int opt = best.second;

        dncs.push_back({l, mid - 1, optl, opt});
        dncs.push_back({mid + 1, r, opt, optr});
    }
    // dncg(start + 1, n - 1, 0, start);
    // dncs(0, start - 1, start, n - 1);

    return ans;
}

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