Submission #363174

#	Time	Username	Problem	Language	Result	Execution time	Memory
363174		Lam_lai_cuoc_doi	Holiday (IOI14_holiday)	C++17	100 / 100	2107 ms	9964 KiB

holiday

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
using ll = long long;
using ld = long double;

const int N = 1e5 + 2;
const ll Inf = 1e17;
int n, s, d;
int a[N], id[N], now[N];
ll dp[N], ans(0);
struct node
{
    int v;
    ll sum;
    node()
    {
        v = sum = 0;
    }
    void combine(const node &a, const node &b)
    {
        v = a.v + b.v;
        sum = a.sum + b.sum;
    }
};
struct SegmentTree
{
    node st[N * 4];
    bool ck[N];
    SegmentTree()
    {
        memset(ck, 0, sizeof ck);
    }
    void Update(int id, int l, int r, int pos, ll v)
    {
        if (l > pos || r < pos)
            return;
        if (l == pos && l == r)
        {
            st[id].v ^= 1;
            st[id].sum += v;
            return;
        }
        Update(id << 1, l, (l + r) / 2, pos, v);
        Update(id << 1 | 1, (l + r) / 2 + 1, r, pos, v);
        st[id].combine(st[id << 1], st[id << 1 | 1]);
    }
    void Update(int v)
    {
        Update(1, 1, n, v, (ck[v] ? -1 : 1) * a[id[v]]);
        ck[v] ^= 1;
    }
    ll Get(int id, int l, int r, int d)
    {
        if (l == r)
            return st[id].sum;
        if (st[id << 1].v >= d)
            return Get(id << 1, l, (l + r) / 2, d);
        else
            return st[id << 1].sum + Get(id << 1 | 1, (l + r) / 2 + 1, r, d - st[id << 1].v);
    }
    ll Get(int d)
    {
        if (d <= 0)
            return 0;
        return Get(1, 1, n, d);
    }
} f;

template <class T>
void Max(T &x, const T &y)
{
    if (x < y)
        x = y;
}

void DAC(int l, int r, int optl, int optr)
{
    if (l > r)
        return;
    int optmid(-1);
    int mid = (l + r) / 2;
    for (int i = r; i > mid; --i)
        f.Update(now[i]);
    for (int i = optl; i <= optr; ++i)
    {
        ll v = f.Get(d - (mid - s + mid - i));
        if (dp[mid] < v)
        {
            dp[mid] = v;
            optmid = i;
        }
        f.Update(now[i]);
    }
    Max(ans, dp[mid]);
    for (int i = optr; i >= optl; --i)
        f.Update(now[i]);
    if (f.ck[now[mid]])
        f.Update(now[mid]);
    DAC(l, mid - 1, optl, optmid);
    for (int i = optl; i < optmid; ++i)
        f.Update(now[i]);
    for (int i = r; i > mid; --i)
        f.Update(now[i]);
    if (!f.ck[now[mid]])
        f.Update(now[mid]);
    DAC(mid + 1, r, optmid, optr);
    for (int i = optl; i < optmid; ++i)
        f.Update(now[i]);
}

void Prepare()
{
    sort(id + 1, id + n + 1, [&](const int &x, const int &y) {
        return a[x] > a[y];
    });
    for (int i = 1; i <= n; ++i)
    {
        now[id[i]] = i;
        dp[i] = -Inf;
    }
    for (int i = 1; i <= n && i < s + d; ++i)
        f.Update(now[i]);
    DAC(s, min(n, s + d - 1), 1, s);
    for (int i = 1; i <= n; ++i)
        if (f.ck[i])
            f.Update(i);
    for (int i = s; i <= n && i <= s + d; ++i)
    {
        f.Update(now[i]);
        ans = max(ans, f.Get(d - (i - s)));
    }
    for (int i = 1; i <= n; ++i)
        if (f.ck[i])
            f.Update(i);
}

ll findMaxAttraction(int input1, int input2, int input3, int arr[])
{
    n = input1;
    s = ++input2;
    d = input3;
    for (int i = 1; i <= n; ++i)
    {
        id[i] = i;
        a[i] = arr[i - 1];
    }
    Prepare();
    reverse(a + 1, a + n + 1);
    s = n - s + 1;
    Prepare();
    return ans;
}

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