제출 #1203049

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1203049		hoangsacura	Holiday (IOI14_holiday)	C++20	30 / 100	192 ms	4680 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>
#define fi first
#define sc second
using namespace std;

const int maxn = 2e5 + 10;
long long f[2 * maxn], g[2 * maxn];
int a[maxn], b[maxn], tmp[maxn], R;
typedef pair<long long, int> LI;

struct IT {
    int cnt[4 * maxn];
    long long sum[4 * maxn];

    void update(int r, int lo, int hi, int u, int val) {
        if (lo == hi) {
            cnt[r] += val;
            sum[r] += tmp[lo] * val;
            return;
        }

        int mid = (lo + hi)/2;

        if (u <= mid)
            update(r * 2, lo, mid, u, val);
        else
            update(r * 2 + 1, mid + 1, hi, u, val);

        sum[r] = sum[r * 2] + sum[r * 2 + 1];
        cnt[r] = cnt[r * 2] + cnt[r * 2 + 1];
    }

    long long get(int r, int lo, int hi, int S) {
        if (lo == hi)
            return tmp[lo] * min(S, cnt[r]);

        int mid = (lo + hi)/2;

        if (cnt[r * 2 + 1] <= S)
            return sum[r * 2 + 1] + get(r * 2, lo, mid, S - cnt[r * 2 + 1]);
        return get(r * 2 + 1, mid + 1, hi, S);
    }
} tree;

int last = 0;
void shift(int a[], int to) {
    while (last < to) {
        tree.update(1, 1, R, a[++last], 1);
    }
    while (last > to) {
        tree.update(1, 1, R, a[last--], -1);
    }
}

void compute(long long f[], int a[], int l, int r, int optL, int optR, bool turn_back) {
    if (l > r || optL > optR)
        return;

    int m = (l + r)/2;



    LI best = LI(0, -2e9);

    for (int i = optL; i <= min(m, optR); ++i) {
        if ((i - 1) + (i - 1) * turn_back > m)
            break;

        shift(a, i);

        best = max(best, LI(tree.get(1, 1, R, m - (i - 1) - (i - 1) * turn_back), -i));
    }


    f[m] = best.fi;
    int opt = -best.sc;

    compute(f, a, l, m - 1, optL, opt, turn_back);
    compute(f, a, m + 1, r, opt, optR, turn_back);
}


long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    ++start;
    for (int i = 1; i <= n; ++i) {
        tmp[i] = attraction[i - 1];
    }

    sort(tmp + 1, tmp + n + 1);
    R = unique(tmp + 1, tmp + n + 1) - tmp - 1;

    for (int i = 1; i <= n; ++i)
        attraction[i - 1] = lower_bound(tmp + 1, tmp + R + 1, attraction[i - 1]) - tmp;

    for (int i = 1; i <= start; ++i)
        a[i] = attraction[i - 1];
    reverse(a + 1, a + start + 1);

    for (int i = start + 1; i <= n; ++i)
        b[i - start] = attraction[i - 1];

    compute(f, a, 1, d, 1, start, 1);
    shift(a, 0);
    compute(g, b, 1, d, 1, n - start, 0);

    long long ans = 0;

    for (int i = 0; i <= d; ++i)
        ans = max(ans, f[i] + g[d - i - 1]);

    shift(b, 0);
    compute(f, a, 1, d, 1, start, 0);
    shift(a, 0);
    compute(g, b, 1, d, 1, n - start, 1);

    for (int i = 0; i <= d; ++i)
        ans = max(ans, g[i] + f[d - i - 2]);

    return ans;
}

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