Submission #1103785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103785		vjudge1	Bitaro's travel (JOI23_travel)	C++17	100 / 100	143 ms	118088 KiB

travel

#include <bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const ll maxn = 1e6 + 2, LG = 21, mod = 1e9 + 7, inf = 1e18;
ll n, a[maxn], L[maxn], R[maxn], d[maxn], st[LG][maxn], low, high, mid, q, s;
vector<int> adj[maxn];
ll getL (int l, int r)
{
    int k = __lg(r - l + 1);
    return max(st[k][l], st[k][r - (1 << k) + 1]);
}
ll getR (int l, int r)
{
    int k = __lg(r - l + 1);
    return min(st[k][l], st[k][r - (1 << k) + 1]);
}
void dfs (int u, int p)
{
    for (int v : adj[u])
    {
        if (v == p) continue;
        d[v] = d[u] + abs(a[u] - a[v]);
        dfs(v, u);
    }
}
int main()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++)
        st[0][i] = (i == 1) ? inf : 2*a[i] - a[i - 1];
    for (int j = 1; j < LG; j++)
        for (int i = 1; i <= n - (1 << (j - 1)); i++)
            st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
    for (int i = 2; i < n; i++)
    {
        low = 1; high = i;
        while (low <= high)
        {
            mid = (low + high)/2;
            if (getL(mid, i) > a[i + 1]) low = mid + 1;
            else high = mid - 1;
        }
        L[i] = high;
    }
    for (int i = 1; i <= n; i++)
        st[0][i] = (i == n) ? -inf : 2*a[i] - a[i + 1];
    for (int j = 1; j < LG; j++)
        for (int i = 1; i <= n - (1 << (j - 1)); i++)
            st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
    for (int i = 2; i < n; i++)
    {
        low = i; high = n;
        while (low <= high)
        {
            mid = (low + high)/2;
            if (getR(i, mid) <= a[i - 1]) high = mid - 1;
            else low = mid + 1;
        }
        R[i] = low;
    }
    for (int i = 2; i < n; i++)
    {
        adj[i].push_back(L[i] ^ R[i] ^ i);
        adj[L[i] ^ R[i] ^ i].push_back(i);
    }
    a[0] = -inf;
    a[n + 1] = inf;
    d[1] = d[n] = a[n] - a[1];
    dfs(1, 0);
    dfs(n, 0);
    cin >> q;
    while (q--)
    {
        cin >> s;
        int r = upper_bound(a + 1, a + n + 1, s) - a, l = r - 1;
        if (s - a[l] <= a[r] - s) cout << abs(s - a[l]) + d[l] << '\n';
        else cout << abs(s - a[r]) + d[r] << '\n';
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 55 / 55