제출 #296573

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
296573		emil_physmath	휴가 (IOI14_holiday)	C++17	24 / 100	5091 ms	9472 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];

void Upd(int v, int vl, int vr, int i, bool add)
{
    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) {
                llong cur;
                ans = max(ans, cur = 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: 0 / 23
• Subtask 3: 17 / 17
• Subtask 4: 0 / 53