제출 #1177187

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177187		MongHwa	Bitaro's travel (JOI23_travel)	C++20	45 / 100	70 ms	5700 KiB

travel

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include <iostream>
#include <algorithm>
using namespace std;

#define ll long long
#define INF 1e17

ll arr[200005];
ll dp[200005];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    for(int i = 1; i <= n; i++)
        cin >> arr[i];

    dp[1] = dp[n] = arr[n]-arr[1];
    for(int i = 2; i < n; i++)
    {
        int l = i-1, r = i+1, pos = i;
        while(1)
        {
            if(l == 0 || r == n+1)
            {
                dp[i] += dp[1];
                break;
            }
            else if(arr[pos]-arr[l] > 100)
            {
                dp[i] += (arr[n]-arr[pos]+dp[1]);
                break;
            }
            else if(arr[r]-arr[pos] > 100)
            {
                dp[i] += (arr[pos]-arr[1]+dp[1]);
                break;
            }

            if(arr[pos]-arr[l] <= arr[r]-arr[pos])
            {
                dp[i] += (arr[pos]-arr[l]);
                pos = l;
                l--;
            }
            else
            {
                dp[i] += (arr[r]-arr[pos]);
                pos = r;
                r++;
            }
        }
    }

    int q;
    cin >> q;
    if(q == 1)
    {
        int x;
        cin >> x;

        int it = lower_bound(arr+1, arr+n+1, x) - arr;
        ll ans = 0; int pos = -1, l = -1, r = -1;
        if(arr[it] == x)
            pos = it, l = it-1, r = it+1;
        else
        {
            ll val1 = INF, val2 = INF;
            if(it > 1)
                val1 = abs(x-arr[it-1]);
            if(it < n+1)
                val2 = abs(x-arr[it]);
            
            if(val1 <= val2)
            {
                ans += abs(x-arr[it-1]);
                pos = it-1, l = pos-1, r = pos+1;
            }
            else
            {
                ans += abs(x-arr[it]);
                pos = it, l = pos-1, r = pos+1;
            }
        }      

        while(l != 0 || r != n+1)
        {
            if(l != 0 && (r == n+1 || arr[pos]-arr[l] <= arr[r]-arr[pos]))
            {
                ans += (arr[pos]-arr[l]);
                pos = l;
                l--;
            }
            else
            {
                ans += (arr[r]-arr[pos]);
                pos = r;
                r++;
            }
        }

        cout << ans << '\n';
        return 0;
    }

    while(q--)
    {
        int x;
        cin >> x;

        int it = lower_bound(arr+1, arr+n+1, x) - arr;
        if(arr[it] == x)
            cout << dp[it] << '\n';
        else
        {
            ll val1 = INF, val2 = INF;
            if(it > 1)
                val1 = abs(x-arr[it-1]);
            if(it < n+1)
                val2 = abs(x-arr[it]);
            
            if(val1 <= val2)
                cout << dp[it-1]+val1 << '\n';
            else
                cout << dp[it]+val2 << '\n';
        }
    }
}

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