Submission #1002227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002227		LonlyR	Bitaro's travel (JOI23_travel)	C++17	100 / 100	137 ms	68432 KiB

travel

#include<bits/stdc++.h>
#define int long long

using namespace std;
const int maxn = 2e5 + 5;
int n, m;
int le[19][maxn], ri[19][maxn], a[maxn], ans[maxn];

int solve(int x)
{
    if (ans[x] != -1) return ans[x];
    int l = x, r = x, pos = a[x], res = 0;
    while (l != 1 || r != n)
    {
        for (int i = 18; i >= 0; i--)
            if (l - (1 << i) >= 1 && le[i][l] <= a[r + 1])
                l -= 1 << i, res += pos - a[l], pos = a[l];
        for (int i = 18; i >= 0; i--)
            if (r + (1 << i) <= n && ri[i][r] < -a[l - 1])
                r += 1 << i, res += a[r] - pos, pos = a[r];
    }
    return ans[x] = res;
}

int qry(int s)
{
	int r = lower_bound(a + 1, a + n + 1, s) - a, l = r - 1;
	if(s - a[l] <= a[r] - s) return s - a[l] + solve(l);
	else return a[r] - s + solve(r);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> n;
    a[0] = -1e12; a[n + 1] = 1e12;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        le[0][i] = a[i] * 2 - a[i - 1], ri[0][i] = a[i + 1] - a[i] * 2;
    for (int j = 1; j < 19; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            ri[j][i] = max(ri[j - 1][i], ri[j - 1][i + (1 << (j - 1))]);
    for (int j = 1; j < 19; j++)
        for (int i = n; i - (1 << j) + 1 >= 1; i--)
            le[j][i] = max(le[j - 1][i], le[j - 1][i - (1 << (j - 1))]);
    memset(ans, -1, sizeof ans);
    cin >> m;
    for (int i = 1, x; i <= m; i++)
        cin >> x, cout << qry(x) << "\n";
}

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