[IOI2016] shortcut

有显然的 \(O(n^3)\) 做法，可以获得 \(38pts\)。（退火在洛谷上能跑 \(75pts\)）

答案具有单调性，考虑二分一个 \(M\) 并判断。列出 \(i\) 到 \(j\) 的距离公式：

求出 \(l_i\) 的前缀和数组 \(L\)，不加边的情况，\(i\) 和 \(j\) 的距离就是 \(L_j-L_i+d_i+d_j\)。
在 \(a,b\) 之间加入一条长度为 \(C\) 的边，距离和 \(|L_i-L_a|+|L_j-L_b|+d_i+d_j+C\) 取 \(\min\)。

注意到，在公式 \(1\) 中，如果值已经 \(\le M\) 的可以不用管。需要计算的是 \(1\) 中 \(\gt M\) 的 \((i,j)\) 中 \(2\) 式的最大值。

绝对值很不好看，将其暴力拆开：

\[L_i+L_j + d_i+d_j+C-M \le L_a+L_b \quad (L_i \ge L_a, L_j \ge L_b) \tag{1}
\]

\[L_i-L_j + d_i+d_j+C-M \le L_a-L_b \quad (L_i \ge L_a, L_j \lt L_b) \tag{2}
\]

\[L_i-L_j - d_i-d_j-C+M \ge L_a-L_b \quad (L_i \lt L_a, L_j \ge L_b) \tag{3}
\]

\[L_i+L_j - d_i-d_j-C+M \ge L_a+L_b \quad (L_i \lt L_a, L_j \lt L_b) \tag{4}
\]

对于公式 \((1)\)，显然若括号内条件不成立，求出的答案一定会更小，无法更新最大值。

对于公式 \((2)(3)(4)\) 也是同理，若括号内条件不成立则不会对不等式的解集产生贡献。

所以，可以不考虑括号内的条件，分别求出上述 \(4\) 个不等式左边的最大/最小值，并考察是否有 \((a,b)\) 满足其不等式。

至于不等式左侧的最值，可以很方便地枚举 \(j\) 并使用单调队列求出最优的 \(i\)。求出左侧的 \(4\) 个最值后，直接枚举 \(b\)，并维护 \(a\) 的两个可行区间，判断是否有交。

结合最外层的二分，本题时间复杂度为 \(O(n \log n)\)，可以通过全部数据。

/**

 * @file:           shortcut.cpp

 * @author:         yaoxi-std

 * @url:

*/

// #pragma GCC optimize ("O2")

// #pragma GCC optimize ("Ofast", "inline", "-ffast-math")

// #pragma GCC target ("avx,sse2,sse3,sse4,mmx")

#include <bits/stdc++.h>

using namespace std;

#define resetIO(x) \

    freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)

#define debug(fmt, ...) \

    fprintf(stderr, "[%s:%d] " fmt "\n", __FILE__, __LINE__, ##__VA_ARGS__)

template <class _Tp>

inline _Tp& read(_Tp& x) {

    bool sign = false; char ch = getchar();

    for (; !isdigit(ch); ch = getchar()) sign |= (ch == '-');

    for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);

    return sign ? (x = -x) : x;

}

template <class _Tp>

inline void write(_Tp x) {

    if (x < 0) putchar('-'), x = -x;

    if (x > 9) write(x / 10);

    putchar((x % 10) ^ 48);

}

bool m_be;

using ll = long long;

const int MAXN = 1e6 + 10;

const int INF = 0x3f3f3f3f;

int n, cst, que[MAXN];

ll len[MAXN], dis[MAXN];

bool check(ll mid) {

    int fr = 1, bk = 0;

    // vmin: min{len[i]-dis[i]}, vmax: max{len[i]+dis[i]}

    ll vmin = 1e18, vmax = -1e18;

    // mx1 ~ mn4 对应 4 个式子

    ll mx1 = -1e18, mx2 = -1e18, mn3 = 1e18, mn4 = 1e18;

    for (int i = 1; i <= n; ++i) {

        if (len[i] + dis[i] - vmin > mid) {

            while (fr <= bk && len[i] - len[que[fr]] + dis[que[fr]] + dis[i] > mid)

                vmax = max(vmax, len[que[fr]] + dis[que[fr]]), ++fr;

            mx1 = max(mx1, vmax + len[i] + dis[i] + cst - mid);

            mx2 = max(mx2, vmax - len[i] + dis[i] + cst - mid);

            mn3 = min(mn3, vmin - len[i] - dis[i] - cst + mid);

            mn4 = min(mn4, vmin + len[i] - dis[i] - cst + mid);

        }

        vmin = min(vmin, len[i] - dis[i]);

        while (fr <= bk && dis[que[bk]] - len[que[bk]] <= dis[i] - len[i]) --bk;

        que[++bk] = i;

    }

    if (mn4 < mx1 || mn3 < mx2) return false;

    int l1 = n + 1, r1 = n, l2 = 1, r2 = 0;

    for (int i = 1; i <= n; ++i) {

        while (l1 > 1 && len[i] + len[l1 - 1] >= mx1) --l1;

        while (l1 <= r1 && len[i] + len[r1] > mn4) --r1;

        while (r2 < n && len[r2 + 1] - len[i] <= mn3) ++r2;

        while (l2 <= r2 && len[l2] - len[i] < mx2) ++l2;

        if (l1 > r1 || l2 > r2) continue;

        if (max(l1, l2) <= min(r1, r2)) return true;

    }

    return false;

}

bool m_ed;

signed main() {

    // resetIO(shortcut);

    // debug("Mem %.5lfMB.", fabs(&m_ed - &m_be) / 1048576);

    read(n), read(cst);

    for (int i = 2; i <= n; ++i) read(len[i]);

    for (int i = 1; i <= n; ++i) read(dis[i]);

    for (int i = 2; i <= n; ++i) len[i] += len[i - 1];

    ll l = 0, r = 1e18, ans = 1e18;

    while (l <= r) {

        ll mid = (l + r) >> 1;

        if (check(mid)) {

            r = mid - 1, ans = mid;

        } else {

            l = mid + 1;

        }

    }

    write(ans), putchar('\n');

    return 0;

}

巴特西

[IOI2016] shortcut

最新文章

热门文章