Submission #362664

#	Time	Username	Problem	Language	Result	Execution time	Memory
362664		RyoPham	Holiday (IOI14_holiday)	C++14	0 / 100	30 ms	6500 KiB

holiday

#define taskname "test"

#include <bits/stdc++.h>
#include "holiday.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 = 1e5 + 5;

int n, start, d;
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 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(k == 0) return 0;
        if(cnt[x] <= k)
            return total[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)
{
    static int curl = 1, curr = 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(start, start + i, mid - i);
        if(k > best)
        {
            best = k;
            opt = i;
        }
    }
    f[mid] = pli(best, start + 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(start - 1 - i, start - 1, mid - i);
        if(k > best)
        {
            best = k;
            opt = i;
        }
    }
    g[mid] = pli(best, start - 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[])
{
    n = _n; start = _start; d = _d;
    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 - 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;
        }
        ans = max(ans, total);
    }
    return ans;
}

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