Submission #362672

#	Time	Username	Problem	Language	Result	Execution time	Memory
362672		RyoPham	Holiday (IOI14_holiday)	C++14	100 / 100	1504 ms	23524 KiB

holiday

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

using namespace std;

#define sz(x) (int)x.size()
#define fi first
#define se second

typedef long long lli;
typedef pair<int, int> pii;
typedef pair<lli, int> pli;

const int maxn = 3e5 + 5;

int si;
int a[maxn];

vector<int> vals;
int m;

pli f[maxn], g[maxn];

struct segment_tree
{
    lli total[maxn * 4];
    int cnt[maxn * 4];

    void init()
    {
        fill(begin(total), end(total), 0);
        fill(begin(cnt), end(cnt), 0);
    }

    void update(int x, int l, int r, int p, int k)
    {
        if(l == r)
        {
            total[x] += k * vals[l];
            cnt[x] += k;
            return;
        }
        int mid = (l + r) / 2;
        if(p <= mid) update(x * 2, l, mid, p, k);
        else update(x * 2 + 1, mid + 1, r, p, k);
        total[x] = total[x * 2] + total[x * 2 + 1];
        cnt[x] = cnt[x * 2] + cnt[x * 2 + 1];
    }

    lli get(int x, int l, int r, int k)
    {
        if(l == r) return vals[l] * 1LL * min(k, cnt[x]);
        int mid = (l + r) / 2;
        if(cnt[x * 2 + 1] <= k)
            return total[x * 2 + 1] + get(x * 2, l, mid, k - cnt[x * 2 + 1]);
        else return get(x * 2 + 1, mid + 1, r, k);
    }
} tree;

lli query(int l, int r, int k, bool flag = false)
{
    static int curl = 1, curr = 0;
    if(flag)
    {
        curl = 1;
        curr = 0;
        tree.init();
        return 0;
    }
    while(curr < r)
    {
        ++curr;
        tree.update(1, 0, m - 1, a[curr], 1);
    }
    while(curr > r)
    {
        tree.update(1, 0, m - 1, a[curr], -1);
        --curr;
    }
    while(curl > l)
    {
        --curl;
        tree.update(1, 0, m - 1, a[curl], 1);
    }
    while(curl < l)
    {
        tree.update(1, 0, m - 1, a[curl], -1);
        ++curl;
    }
    return tree.get(1, 0, m - 1, k);
}

void dnc_f(int l, int r, int optl, int optr)
{
    if(l > r) return;
    int mid = (l + r) / 2;
    lli best = -1, opt = 0;
    for(int i = optl; i <= min(mid, optr); ++i)
    {
        lli k = query(si, si + i, mid - i);
        if(k > best)
        {
            best = k;
            opt = i;
        }
    }
    f[mid] = pli(best, si + opt);
    dnc_f(l, mid - 1, optl, opt);
    dnc_f(mid + 1, r, opt, optr);
}

void dnc_g(int l, int r, int optl, int optr)
{
    if(l > r) return;
    int mid = (l + r) / 2;
    lli best = -1, opt = 0;
    for(int i = optl; i <= min(mid, optr); ++i)
    {
        lli k = query(si - 1 - i, si - 1, mid - i);
        if(k > best)
        {
            best = k;
            opt = i;
        }
    }
    g[mid] = pli(best, si - 1 - opt);
    dnc_g(l, mid - 1, optl, opt);
    dnc_g(mid + 1, r, opt, optr);
}

lli findMaxAttraction(int n, int start, int d, int attraction[])
{
    si = start;
    for(int i = 0; i < n; ++i)
    {
        a[i] = attraction[i];
        vals.push_back(a[i]);
    }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    m = sz(vals);
    for(int i = 0; i < n; ++i)
        a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();
    dnc_f(0, d, 0, n - 1 - start);
    if(start > 0)
        dnc_g(0, d, 0, start - 1);
    lli ans = 0;
    for(int i = 0; i <= d; ++i)
    {
        lli total = f[i].fi;
        if(start > 0)
        {
            int p = f[i].se;
            int left = d - i - (p - (start - 1));
            if(left >= 0)
                total += g[left].fi;
        }
        assert(total >= f[i].fi);
        ans = max(ans, total);
    }
    reverse(a, a + n);
    si = start = n - start - 1;
    query(1, 0, 0, true);
    dnc_f(0, d, 0, n - 1 - start);
    if(start > 0)
        dnc_g(0, d, 0, start - 1);
    for(int i = 0; i <= d; ++i)
    {
        lli total = f[i].fi;
        if(start > 0)
        {
            int p = f[i].se;
            int left = d - i - (p - (start - 1));
            if(left >= 0)
                total += g[left].fi;
        }
        assert(total >= f[i].fi);
        ans = max(ans, total);
    }
    return ans;
}

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