Submission #1213764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213764		jerzyk	Bitaro's travel (JOI23_travel)	C++20	100 / 100	222 ms	8312 KiB

travel

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1'000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1'000'000'007LL;
const int N = 1<<18;
ll tab[N];
int drzmi[2 * N], drzma[2 * N];

int GetL(int v, int x)
{
    v += N;
    while(v > 1)
    {
        if(v % 2 == 1 && drzma[v - 1] > x)
            {--v; break;}
        v /= 2;
    }
    //if(v == 1) return -1;
    while(v < N)
    {
        v *= 2;
        if(drzma[v + 1] >= x) ++v;
    }
    return v - N;
}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   

int GetR(int v, int x)
{
    v += N;
    while(v > 1)
    {
        if(v % 2 == 0 && drzmi[v + 1] <= x)
            {++v; break;}
        v /= 2;
    }
    //if(v == 1) return -1;
    while(v < N)
    {
        v *= 2; ++v;
        if(drzmi[v - 1] <= x) --v;
    }
    return v - N;
}

ll Query(int n, ll s)
{
    ll ans = 0LL;
    int cur = (lower_bound(tab + 1, tab + 1 + n, s) - tab);
    if(tab[cur] - s >= s - tab[cur - 1])
        --cur;
    ans = tab[cur] - s;
    if(ans < 0) ans *= -1LL;
    int l = cur, r = cur, a;
    while(l != 1 || r != n)
    {
        // cout << "Q: " << l << " " << r << " " << cur << "\n";
        // cout << tab[l - 1] << " " << tab[r + 1] << "\n";
        if(tab[cur] - tab[l - 1] <= tab[r + 1] - tab[cur])
        {
            // cout << "L:\n";
            a = GetL(l, tab[r + 1]);
            ans += tab[cur] - tab[a];
            l = a; cur = a;
        }else
        {
            // cout << "R:\n";
            a = GetR(r, tab[l - 1]);
            ans += tab[a] - tab[cur];
            r = a; cur = a;
        }
    }
    return ans;
}

void Solve()
{
    int n, q, a;
    cin >> n;   
    for(int i = 1; i <= n; ++i)
        cin >> tab[i];
    tab[n + 1] = II + 100;
    tab[0] = -II;
    drzmi[n + N] = -II - 300;
    for(int i = 1; i < n; ++i)
        drzmi[i + N] = tab[i] - (tab[i + 1] - tab[i]);
    drzma[1 + N] = II + 300;
    for(int i = 2; i <= n; ++i)
        drzma[i + N] = tab[i] + (tab[i] - tab[i - 1]);
    for(int v = N - 1; v >= 1; --v)
    {
        drzmi[v] = min(drzmi[v * 2], drzmi[v * 2 + 1]);
        drzma[v] = max(drzma[v * 2], drzma[v * 2 + 1]);
    }
    cin >> q;
    for(int i = 1; i <= q; ++i)
    {
        cin >> a;
        ll ans = 0LL;
        ans = Query(n, a);
        cout << ans << "\n";
    }
}

int main()
{
    for(int i = 1; i < 2 * N; ++i) drzmi[i] = II;
    for(int i = 1; i < 2 * N; ++i) drzma[i] = -II;
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

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