제출 #1103853

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1103853		vjudge1	Bitaro's travel (JOI23_travel)	C++17	100 / 100	91 ms	36676 KiB

travel

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e6 + 6;
const ll mod = 1e9 + 7;
const ll inf = LLONG_MAX/4;
#define bit(x,y) ((x >> y) & 1)

vector<ll> g[N];
ll a[N];
ll d[N];
int n;
void build(ll x, ll dis)
{
    d[x] = dis + a[n] - a[1];
    for(auto y : g[x])
    {
        build(y, dis + abs(a[x] - a[y]));
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    int i,j;
    for(i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    a[0] = -inf;
    a[n + 1] = inf;
    stack<pair<ll,ll>> st;
    st.push({1,inf});
    for(i = 2;i <= n - 1;i++)
    {
        if(a[i] - a[i - 1] <= a[i + 1] - a[i])
        {
            while(st.top().second <= a[i + 1]) st.pop();
            j = st.top().first;
            g[j].push_back(i);
        }
        while(st.top().second <= 2 * a[i] - a[i - 1]) st.pop();
        st.push({i,2 * a[i] - a[i - 1]});
    }
    while(!st.empty()) st.pop();
    st.push({n,inf});
    for(i = n - 1;i >= 2;i--)
    {
        if(a[i] - a[i - 1] > a[i + 1] - a[i])
        {
            while(st.top().second < -a[i - 1]) st.pop();
            j = st.top().first;
            g[j].push_back(i);
        }
        while(st.top().second <= a[i + 1] - 2 * a[i]) st.pop();
        st.push({i,a[i + 1] - 2 * a[i]});
    }
    build(1,0);
    build(n,0);
    //for(i = 1;i <= n;i++) cout << d[i] << " ";
    ll q;
    cin >> q;
    while(q--)
    {
        ll x;
        cin >> x;
        if(x < a[1]) i = 1;
        if(x > a[n]) i = n;
        ll l = 1, r = n;
        while(true)
        {
            if(l == r)
            {
                i = l;
                break;
            }
            ll mid = (l + r + 1) / 2;
            if(a[mid] <= x) l = mid;
            else r = mid - 1;
        }
        if(x - a[l] <= a[l + 1] - x) i = l;
        else i = l + 1;
        cout << abs(x - a[i]) + d[i] << "\n";
    }
}//sus

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