Submission #536131

#	Time	Username	Problem	Language	Result	Execution time	Memory
536131		KoD	Shortcut (IOI16_shortcut)	C++17	100 / 100	1599 ms	92248 KiB

shortcut

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

using ll = long long;

constexpr ll inf = std::numeric_limits<ll>::max() / 2;

using std::vector;
using std::array;
using std::pair;
using std::tuple;

ll find_shortcut(int N, vector<int> L, vector<int> D, int C) {
    vector<ll> X(N);
    for (int i = 0; i < N - 1; ++i) {
        X[i + 1] = X[i] + L[i];
    }
    vector<int> ord(N);
    std::iota(ord.begin(), ord.end(), 0);
    std::sort(ord.begin(), ord.end(), [&](const int i, const int j) {
        return X[i] + D[i] < X[j] + D[j];
    });
    vector<pair<ll, int>> sum(N);
    vector<tuple<ll, ll, int>> dif(N + 1);
    dif[N] = {inf, inf, -1};
    for (int i = N - 1; i >= 0; --i) {
        const int k = ord[i];
        sum[i] = {X[k] + D[k], k};
        if (X[k] - D[k] < std::get<0>(dif[i + 1])) {
            dif[i] = {X[k] - D[k], std::get<0>(dif[i + 1]), k};
        } else {
            dif[i] = dif[i + 1];
            std::get<1>(dif[i]) = std::min(std::get<1>(dif[i]), X[k] - D[k]);
        }
    }
    std::sort(ord.begin(), ord.end(), [&](const int i, const int j) {
        return X[i] - D[i] < X[j] - D[j];
    });
    vector<int> lowb(N);
    const auto check = [&](const ll thres) {
        ll a = -inf, b = inf, c = -inf, d = inf;
        int upb = 0;
        for (const int i : ord) {
            while (upb < N and sum[upb].first <= thres + X[i] - D[i]) upb += 1;
            if (upb == N) continue;
            if (upb == N - 1 and sum[upb].second == i) continue;
            const ll max_sum = sum[N - 1].second == i ? sum[N - 2].first : sum[N - 1].first;
            a = std::max(a, max_sum + X[i] + D[i] + C - thres);
            c = std::max(c, max_sum - X[i] + D[i] + C - thres);
            const ll min_dif = std::get<2>(dif[upb]) == i ? std::get<1>(dif[upb]) : std::get<0>(dif[upb]);
            b = std::min(b, min_dif + X[i] - D[i] - C + thres);
            d = std::min(d, min_dif - X[i] - D[i] - C + thres);
        }
        int idx = 0;
        for (int i = N - 1; i >= 0; --i) {
            while (idx < N and X[idx] < a - X[i]) idx += 1;
            lowb[i] = idx;
        }
        idx = 0;
        for (int i = 0; i < N; ++i) {
            while (idx < N and X[idx] < c + X[i]) idx += 1;
            const int k = std::max(lowb[i], idx);
            if (k < N and X[k] <= std::min(b - X[i], d + X[i])) return true;
        }
        return false;
    };
    ll ok = inf, ng = 0;
    while (ok - ng > 1) {
        const ll md = (ok + ng) / 2;
        (check(md) ? ok : ng) = md;
    }
    return ok;
}

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 33 / 33
• Subtask 6: 22 / 22
• Subtask 7: 4 / 4
• Subtask 8: 3 / 3