Submission #799568

#	Time	Username	Problem	Language	Result	Execution time	Memory
799568		becaido	Shortcut (IOI16_shortcut)	C++17	100 / 100	1063 ms	61944 KiB

shortcut

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "shortcut.h"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const ll INF = 1e18;
const int SIZE = 1e6 + 5;

int n, c;
ll x[SIZE];
int d[SIZE];

bool ok(ll k) {
    ll A, B, C, D, mn, mx;
    A = C = mx = -INF;
    B = D = mn = INF;
    deque<pair<ll, ll>> st;
    FOR (i, 1, n) {
        if (mn < x[i] + d[i] - k) {
            B = min(B, x[i] - d[i] + mn + k - c);
            C = max(C, x[i] + d[i] - mn - k + c);
        }
        while (st.size() && st[0].F < x[i] + d[i] - k) {
            mx = max(mx, st[0].S);
            st.pop_front();
        }
        A = max(A, x[i] + d[i] + mx - k + c);
        D = min(D, x[i] - d[i] - mx + k - c);
        mn = min(mn, x[i] - d[i]);
        while (st.size() && x[i] - d[i] <= st.back().F && x[i] + d[i] >= st.back().S) st.pop_back();
        if (!st.size() || x[i] + d[i] > st.back().S) st.pb(x[i] - d[i], x[i] + d[i]);
    }
    if (A > B || C > D) return 0;
    int l1 = n + 1, r1 = n, l2 = 1, r2 = 0;
    FOR (i, 1, n) {
        while (l1 > 1 && A - x[i] <= x[l1 - 1]) l1--;
        while (r1 >= 1 && x[r1] > B - x[i]) r1--;
        while (l2 <= n && C + x[i] > x[l2]) l2++;
        while (r2 < n && x[r2 + 1] <= D + x[i]) r2++;
        if (max(l1, l2) <= min(r1, r2)) return 1;
    }
    return 0;
}

ll find_shortcut(int _n, vector<int> _l, vector<int> _d, int _c) {
    n = _n, c = _c;
    FOR (i, 0, n - 1) {
        if (i >= 1) x[i + 1] = x[i] + _l[i - 1];
        d[i + 1] = _d[i];
    }
    ll l = 0, r = 0, mx = -INF;
    FOR (i, 1, n) {
        r = max(r, d[i] + x[i] + mx);
        mx = max(mx, d[i] - x[i]);
    }
    while (l < r) {
        ll mid = (l + r) / 2;
        if (ok(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

#ifdef WAIMAI
int main() {
    int n, c;
    assert(2 == scanf("%d%d", &n, &c));

    vector<int> l(n - 1);
    vector<int> d(n);
    for (int i = 0; i < n - 1; i++)
        assert(1 == scanf("%d", &l[i]));
    for (int i = 0; i < n; i++)
        assert(1 == scanf("%d", &d[i]));

    ll t = find_shortcut(n, l, d, c);


    printf("%lld\n", t);

    return 0;
}
#endif

• 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