Submission #296581

#	Time	Username	Problem	Language	Result	Execution time	Memory
296581		emil_physmath	Holiday (IOI14_holiday)	C++17	47 / 100	1342 ms	9660 KiB

holiday

#include <iostream>
#include <algorithm>
#include"holiday.h"
using namespace std;
using llong = long long;
#define BUGO(x) cerr << #x << ": " << x << '\n';

const int pool = 1000'000;
int nodes = 1;
int lson[pool], rson[pool], cnt[pool];
llong sum[pool];

int cnt2[101];

void Upd(int v, int vl, int vr, int i, bool add)
{
    if (i <= 100 && v == 1)
    {
        if (add) ++cnt2[i];
        else --cnt2[i];
    }
    if (vl == vr)
    {
        if (add)
            sum[v] += i, ++cnt[v];
        else
            sum[v] -= i, --cnt[v];
        return;
    }
    if (lson[v] == -1)
    {
        lson[v] = ++nodes;
        rson[v] = ++nodes;
    }
    int vm = vl + (vr - vl) / 2;
    if (i <= vm)
        Upd(lson[v], vl, vm, i, add);
    else
        Upd(rson[v], vm + 1, vr, i, add);
    sum[v] = sum[lson[v]] + sum[rson[v]];
    cnt[v] = cnt[lson[v]] + cnt[rson[v]];
}
llong Get(int v, int vl, int vr, int x)
{
    if (x == 0) return 0;
    if (cnt[v] <= x) return sum[v];
    int vm = vl + (vr - vl) / 2;
    if (cnt[rson[v]] >= x)
        return Get(rson[v], vm + 1, vr, x);
    return Get(lson[v], vl, vm, x - cnt[rson[v]]) + sum[rson[v]];
}
long long int findMaxAttraction(int n, int start, int d, int a[]) {
    fill(lson, lson + pool, -1);
    fill(rson, rson + pool, -1);
    int maxA = (n <= 3000 ? 1000'000'000 : 100);
    llong ans = 0;
    for (int l = start; l >= 0; --l)
    {
        Upd(1, 0, maxA, a[l], true);
        for (int r = start; r < n; ++r)
        {
            if (r > start)
                Upd(1, 0, maxA, a[r], true);
            int move = start - l + r - start + min(start - l, r - start);
            if (d - move > 0)
            {
                if (maxA == 100)
                {
                    llong cur = 0;
                    int lft = d - move;
                    for (int i = 100; i >= 1; --i)
                        if (cnt2[i] >= lft) {
                            cur += lft * (llong)i;
                            break;
                        }
                        else {
                            cur += cnt2[i] * (llong)i;
                            lft -= cnt2[i];
                        }
                    ans = max(ans, cur);
                }
                else
                    ans = max(ans, Get(1, 0, maxA, d - move));
            }
        }
        for (int r = start; r < n; ++r)
            if (r > start)
                Upd(1, 0, maxA, a[r], false);
    }
    return ans;
}

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