Submission #775716

#	Time	Username	Problem	Language	Result	Execution time	Memory
775716		danikoynov	Holiday (IOI14_holiday)	C++14	100 / 100	1068 ms	14244 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 100100;

struct node
{
    ll sum, act;

    node(ll _sum = 0, ll _act = 0)
    {
        sum = _sum;
        act = _act;
    }
};

node merge_node(node lf, node rf)
{
    node nd;
    nd.sum = lf.sum + rf.sum;
    nd.act = lf.act + rf.act;
    return nd;
}

ll value[maxn], pos[maxn];
node tree[4 * maxn];
int n;

void toggle(int root, int left, int right, int pos, int type)
{
    if (left == right)
    {
        if (type == 1)
        {
            tree[root].sum = value[left];
            tree[root].act = 1;
        }
        else
        {
            tree[root].sum = 0;
            tree[root].act = 0;
        }
        return;
    }

    int mid = (left + right) / 2;
    if (pos <= mid)
        toggle(root * 2, left, mid, pos, type);
    else
        toggle(root * 2 + 1, mid + 1, right, pos, type);

    tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
    ///cout << "back " << root << " " << tree[root].sum << " " << pos << " " << type << endl;
}

ll get_sum(int root, int left, int right, int k)
{
    if (tree[root].act == 0 || k == 0)
        return 0;

    if (tree[root].act <= k)
        return tree[root].sum;

    int mid = (left + right) / 2;
    if (tree[root * 2 + 1].act >= k)
        return get_sum(root * 2 + 1, mid + 1, right, k);
    return get_sum(root * 2, left, mid, k - tree[root * 2 + 1].act) + tree[root * 2 + 1].sum;
}

int lf, rf;
void cost(int left, int right)
{
    /**for (int i = 0; i < 4 * n; i ++)
        tree[i] = node();
    for (int i = left; i <= right; i ++)
        toggle(1, 0, n - 1, pos[i], 1);
    return;*/
    while(rf < right)
    {
        rf ++;
        toggle(1, 0, n - 1, pos[rf], 1);
        ///cout << "activate " << value[pos[rf]] << " " << pos[rf] << endl;
    }

    while(lf > left)
    {
        lf --;
        toggle(1, 0, n - 1, pos[lf], 1);
    }

    while(rf > right)
    {
        toggle(1, 0, n - 1, pos[rf], 0);
        rf --;
    }

    while(lf < left)
    {
        ///cout << "deactivate " << value[pos[lf]] << " " << pos[lf] << endl;
        toggle(1, 0, n - 1, pos[lf], 0);
        lf ++;
    }
}

int pivot, hol;
ll dp_after[maxn * 3], dp_before[maxn * 3];
void divide_after(int left, int right, int optl, int optr)
{
    if (left > right)
        return;

    int mid = (left + right) / 2;
    int opt = -1;
    dp_after[mid] = -1;
    for (int i = max(pivot, optl); i <= min(n - 1, optr); i ++)
    {
        cost(pivot, i);
        ll cur = 0;
        if (mid - (i - pivot) > 0)
            cur = get_sum(1, 0, n - 1, mid - (i - pivot));
            ///cout << i << " :: " << cur << " " << mid - (i - pivot) << endl;
        if (cur > dp_after[mid])
        {
            dp_after[mid] = cur;
            opt = i;
        }
    }
    if (opt == -1)
    {
        opt = optl;
        dp_after[mid] = 0;
    }
    ///cout << "divide_after " << mid << " " << opt << " " << dp_after[mid] << " " << optl << " " << optr << endl;
    divide_after(left, mid - 1, optl, opt);
    divide_after(mid + 1, right, opt, optr);
}

void divide_before(int left, int right, int optl, int optr)
{

    if (left > right)
        return;

    int mid = (left + right) / 2;
    int opt = -1;
    dp_before[mid] = -1;
    for (int i = max(0, optl); i <= min(pivot - 1, optr); i ++)
    {
        cost(i, pivot - 1);
        ll cur = 0;
        if (mid - (pivot - i) * 2 > 0)
            cur = get_sum(1, 0, n - 1, mid - (pivot - i) * 2);
        ///cout << i << " : " << mid - (pivot - i) * 2 << " " << cur << endl;
        if (cur >= dp_before[mid])
        {
            dp_before[mid] = cur;
            opt = i;
        }
    }
    if (opt == -1)
    {

        opt = optl;
        dp_before[mid] = 0;
    }
    ///cout << "divide before " << mid << " " << opt << " " << dp_before[mid] << " " << optl << " " << optr << endl;
    divide_before(left, mid - 1, opt, optr);
    divide_before(mid + 1, right, optl, opt);
}

ll action(int attraction[])
{
    /**cout << "---------------" << endl;
    for (int i = 0; i < n; i ++)
        cout << attraction[i] << " ";
    cout << endl;*/
    vector < pair < int, int > > pr;
    for (int i = 0; i < n; i ++)
    {
        pr.push_back({attraction[i], i});

    }

    sort(pr.begin(), pr.end());
    for (int i = 0; i < n; i ++)
    {
        value[i] = pr[i].first;
        pos[pr[i].second] = i;
    }

    for (int i = 0; i < 4 * n; i ++)
        tree[i] = node();
    lf = 0;
    rf = -1;
    divide_after(0, hol, pivot, n - 1);

    for (int i = 0; i < 4 * n; i ++)
        tree[i] = node();
    lf = 0;
    rf = -1;
    divide_before(0, hol, 0, pivot - 1);

    for (int i = 1; i <= hol; i ++)
    {
        dp_after[i] = max(dp_after[i], dp_after[i - 1]);
        dp_before[i] = max(dp_before[i], dp_before[i - 1]);
    }
    /**for (int i = 0; i <= hol; i ++)
        cout << dp_after[i] << " ";
    cout << endl;*/
    ll ans = 0;
    for (int i = 0; i <= hol; i ++)
    {
        ///cout << dp_before[i] << " " << dp_after[hol - i] << " " << i << " " << hol - i << endl;
        ans = max(ans, dp_before[i] + dp_after[hol - i]);
        ///cout << ans << endl;
    }
        ///cout << ans << endl;

    return ans;
}
long long int findMaxAttraction(int N, int start, int d, int attraction[])
{
    pivot = start;
    hol = d;
    n = N;
    ll ans = action(attraction);

    start = N - start - 1;
    pivot = start;
    reverse(attraction, attraction + N);
    ans = max(ans, action(attraction));
    return ans;
}

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