Submission #1103761

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

travel

#include <bits/stdc++.h>
using namespace std;

long long a[200005], ans[200005];
vector<long long> adj[200005];
stack<long long> st;

void dfs(long long x)
{
    for (auto y: adj[x])
    {
        ans[y]=ans[x]+abs(a[x]-a[y]);
        dfs(y);
    };
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, q, i, j, k;
    cin >> n;
    for (i=1; i<=n; i++)
    {
        cin >> a[i];
    };
    for (i=2; i<n; i++)
    {
        if (a[i]-a[i-1]<=a[i+1]-a[i])
        {
            while (!st.empty() && a[st.top()]-a[st.top()-1]<=a[i+1]-a[st.top()]) {st.pop();};
            if (st.empty()) {adj[1].push_back(i);}
            else {adj[st.top()].push_back(i);};
        }
        else {st.push(i);};
    };
    while (!st.empty()) {st.pop();};
    for (i=n-1; i>1; i--)
    {
        if (a[i]-a[i-1]>a[i+1]-a[i])
        {
            while (!st.empty() && a[st.top()+1]-a[st.top()]<a[st.top()]-a[i-1]) {st.pop();};
            if (st.empty()) {adj[n].push_back(i);}
            else {adj[st.top()].push_back(i);};
        }
        else {st.push(i);};
    };
    ans[1]=ans[n]=a[n]-a[1];
    dfs(1);
    dfs(n);
    cin >> q;
    while (q--)
    {
        cin >> i;
        j=upper_bound(a+1, a+n+1, i)-a-1;
        k=j+1;
        if (j==0) {cout << abs(i-a[k])+ans[k] << "\n";}
        else if (k==n+1) {cout << abs(i-a[j])+ans[j] << "\n";}
        else if (i-a[j]<=a[k]-i) {cout << abs(i-a[j])+ans[j] << "\n";}
        else {cout << abs(i-a[k])+ans[k] << "\n";};
    };
}

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