제출 #1158863

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1158863		hungnt	Holiday (IOI14_holiday)	C++20	100 / 100	930 ms	16116 KiB

holiday

#include "holiday.h"
#include "bits/stdc++.h"
#define fi first
#define sc second
using namespace std;

using ll = long long;
using pll = pair<ll, ll>;
const ll maxn = 300005;
ll n;
ll a[maxn];
ll d;
ll st;
ll opt[maxn];
pll t[2 * maxn];
ll ls[2 * maxn], rs[2 * maxn], tsz = 0, root = 0;
ll id[maxn];
pll b[maxn];

void init(ll &v, ll tl, ll tr)
{
    if (!v)
        v = ++tsz;
    if (tl == tr)
    {
        t[v] = {0, 0};
        return;
    }
    ll mid = (tl + tr) / 2;
    init(ls[v], tl, mid);
    init(rs[v], mid + 1, tr);
    t[v] = {0, 0};
}

ll get(ll v, ll tl, ll tr, ll k)
{
    if (k == 0)
        return 0;
    if (k >= t[v].sc)
        return t[v].fi;
    ll mid = (tl + tr) / 2;
    if (k >= t[rs[v]].sc)
        return t[rs[v]].fi + get(ls[v], tl, mid, k - t[rs[v]].sc);
    return get(rs[v], mid + 1, tr, k);
}

void upd(ll v, ll tl, ll tr, ll i, bool e)
{
    if (v == root)
    {
        i = id[i];
    }
    if (tl == tr)
    {
        if (e)
            t[v] = {b[i].fi, 1};
        else
            t[v] = {0, 0};
        return;
    }
    ll mid = (tl + tr) / 2;
    if (i <= mid)
        upd(ls[v], tl, mid, i, e);
    else
        upd(rs[v], mid + 1, tr, i, e);
    t[v] = {t[ls[v]].fi + t[rs[v]].fi, t[ls[v]].sc + t[rs[v]].sc};
}

ll cr;
ll dpr[maxn];
ll dpl[maxn];
bool bf = 0;

void dp(ll l, ll r, ll tl, ll tr)
{
    if (l > r)
        return;
    ll mid = (l + r) / 2;
    if (bf)
        tl = st, tr = n;
    while (cr > tl)
    {
        upd(root, 1, n, cr, 0);
        cr--;
    }
    while (cr < tl)
    {
        upd(root, 1, n, cr + 1, 1);
        cr++;
    }
    opt[mid] = -1;
    dpr[mid] = -1;
    for (ll i = tl; i <= tr; i++)
    {
        ll ck = mid - 2 * (i - st);
        if (ck < 0)
            break;
        ll cur = get(root, 1, n, ck);
        if (cur > dpr[mid])
        {
            dpr[mid] = cur;
            opt[mid] = i;
        }
        if (i < n)
        {
            upd(root, 1, n, i + 1, 1);
            cr = i + 1;
        }
    }
    if (opt[mid] != -1)
    {
        dp(l, mid - 1, tl, opt[mid]);
        dp(mid + 1, r, opt[mid], tr);
    }
    else
    {
        dp(l, mid - 1, tl, tr);
        dp(mid + 1, r, tl, tr);
    }
    dpr[mid] = max(dpr[mid], 0LL);
}

void dp2(ll l, ll r, ll tl, ll tr)
{
    if (l > r)
        return;
    ll mid = (l + r) / 2;
    if (bf)
        tl = 1, tr = st - 1;
    while (cr < tr)
    {
        upd(root, 1, n, cr, 0);
        cr++;
    }
    while (cr > tr)
    {
        upd(root, 1, n, cr - 1, 1);
        cr--;
    }
    opt[mid] = -1;
    dpl[mid] = -1;
    for (ll i = tr; i >= tl; i--)
    {
        ll ck = mid - (st - i);
        if (ck < 0)
            continue;
        ll cur = get(root, 1, n, ck);
        if (cur > dpl[mid])
        {
            dpl[mid] = cur;
            opt[mid] = i;
        }
        if (i > 1)
        {
            upd(root, 1, n, i - 1, 1);
            cr = i - 1;
        }
    }
    if (opt[mid] != -1)
    {
        dp2(mid + 1, r, tl, opt[mid]);
        dp2(l, mid - 1, opt[mid], tr);
    }
    else
    {
        dp2(mid + 1, r, tl, tr);
        dp2(l, mid - 1, tl, tr);
    }
    dpl[mid] = max(dpl[mid], 0LL);
}

ll reshi()
{
    for (ll i = 1; i <= n; i++)
        b[i] = {a[i], i};
    sort(b + 1, b + 1 + n);
    for (ll i = 1; i <= n; i++)
        id[b[i].sc] = i;
    init(root, 1, n);
    cr = st;
    upd(root, 1, n, st, 1);
    for (ll i = 0; i <= d; i++)
        dpr[i] = dpl[i] = opt[i] = 0;
    dp(1, d, st, n);
    for (ll i = 0; i <= d; i++)
        dpl[i] = opt[i] = 0;
    init(root, 1, n);
    cr = st - 1;
    if (cr)
        upd(root, 1, n, cr, 1);
    dp2(2, d, 1, st - 1);
    ll ans = 0;
    dpl[0] = dpl[1] = dpr[0] = 0;
    for (ll i = 0; i <= d; i++)
        ans = max(ans, dpl[i] + dpr[d - i]);
    return ans;
}

ll findMaxAttraction(int N, int str, int D, int attraction[])
{
    n = N, d = D, st = str + 1;
    for (ll i = 1; i <= n; i++)
        a[i] = attraction[i - 1];
    ll ans = reshi();
    reverse(a + 1, a + 1 + n);
    st = n - st + 1;
    ans = max(ans, reshi());
    return ans;
}

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