Submission #676819

#	Time	Username	Problem	Language	Result	Execution time	Memory
676819		bashkort	Holiday (IOI14_holiday)	C++17	100 / 100	668 ms	51764 KiB

holiday

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

using namespace std;
using ll = long long;

constexpr int N = 100007;
constexpr int N_ = N * 18;
constexpr ll inf = 1e15;

struct Info {
    ll sum = 0;
    int cnt = 0;
};

int node_cnt = 1;

int L[N_], R[N_];
Info t[N_];

int create(int x) {
    int nx = node_cnt++;
    L[nx] = L[x], R[nx] = R[x], t[nx] = t[x];
    return nx;
}

void clear() {
    node_cnt = 1;
}

int modify(int i, int val, int x, int lx, int rx) {
    int nx = create(x);
    ++t[nx].cnt, t[nx].sum += val;

    if (lx + 1 < rx) {
        int mid = (lx + rx) >> 1;

        if (i < mid) {
            L[nx] = modify(i, val, L[x], lx, mid);
        } else {
            R[nx] = modify(i, val, R[x], mid, rx);
        }
    }

    return nx;
}

ll kth_sum(int k, int x, int lx, int rx) {
    if (lx + 1 == rx) {
        return t[x].sum;
    }

    int mid = (lx + rx) >> 1;

    if (t[R[x]].cnt > k) {
        return kth_sum(k, R[x], mid, rx);
    } else {
        k -= t[R[x]].cnt;
        return t[R[x]].sum + (k == 0 ? 0 : kth_sum(k, L[x], lx, mid));
    }
}

vector<ll> work(int d, vector<int> a) {
    if (a.empty()) {
        return vector<ll>(d + 1);
    }
    clear();
    int n = a.size();
    vector<pair<int, int>> yy;
    for (int i = 0; i < n; ++i) {
        if (a[i]) {
            yy.emplace_back(a[i], i);
        }
    }
    sort(yy.begin(), yy.end());

    vector<int> root(n);
    auto getValue = [&](int i, int opt) -> ll {
        if (i >= opt) {
            return 0;
        }

        return kth_sum(opt - i, root[i], 0, yy.size());
    };

    vector<pair<int, int>> stk; //i, opt

    int last = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] == 0) {
            continue;
        }
        int p = lower_bound(yy.begin(), yy.end(), pair{a[i], i}) - yy.begin();

        root[i] = modify(p, a[i], last, 0, yy.size());
        last = root[i];

        while (!stk.empty()) {
            auto [j, opt] = stk.back();

            if (getValue(j, opt) < getValue(i, opt)) {
                stk.pop_back();
            } else {
                break;
            }
        }

        if (stk.empty()) {
            stk.emplace_back(i, 0);
        } else {
            auto [j, opt] = stk.back();

            int lo = opt, hi = d + 1;
            while (lo + 1 < hi) {
                int mid = (lo + hi) >> 1;

                if (getValue(j, mid) < getValue(i, mid)) {
                    hi = mid;
                } else {
                    lo = mid;
                }
            }

            if (hi <= d) {
                stk.emplace_back(i, hi);
            }
        }
    }

    vector<ll> ans(d + 1);
    for (int i = d; i > 0; --i) {
        if (stk.empty()) {
            break;
        }

        ans[i] = getValue(stk.back().first, i);

        if (stk.back().second == i) {
            stk.pop_back();
        }
    }

    return ans;
}

ll solve(int n, int start, int d, vector<int> a) {
    vector<int> left, right;
    for (int i = start - 1; i >= 0; --i) {
        left.push_back(a[i]);
    }
    for (int i = start; i < n; ++i) {
        right.push_back(a[i]);
    }

    vector<ll> ansL = work(d, left);
    vector<ll> ansR = work(d, right);

    ll ans = 0;
    for (int i = 0; i <= d; ++i) {
        ans = max(ans, ansR[i]);
        if (i != d) {
            ans = max(ans, ansR[i] + ansL[d - i - 1]);
        }
    }

    return ans;
}

ll findMaxAttraction(int n, int start, int d, int attraction[]) {
    ll ans = 0;
    for (int _ = 0; _ < 2; ++_) {
        vector<int> now;
        for (int i = 0; i < start; ++i) {
            now.push_back(attraction[i]);
            now.push_back(0);
        }
        int s = now.size();
        for (int i = start; i < n; ++i) {
            now.push_back(attraction[i]);
        }

        ans = max(ans, solve(now.size(), s, d, now));

        reverse(attraction, attraction + n);
        start = n - start - 1;
    }
    return ans;
}

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