Submission #1177039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177039		MongHwa	Bitaro's travel (JOI23_travel)	C++20	0 / 100	70 ms	6468 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], psum[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];
        psum[i] = psum[i-1] + 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
        {
            int 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(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 ans = INF;
            if(it > 1)
                ans = min(ans, dp[it-1]+abs(x-arr[it-1]));
            if(it < n+1)
                ans = min(ans, dp[it]+abs(x-arr[it]));
            cout << ans << '\n';
        }
    }
}

Compilation message (stderr)

travel.cpp: In function 'int main()':
travel.cpp:8:13: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+17' to '2147483647' [-Woverflow]
    8 | #define INF 1e17
      |             ^~~~
travel.cpp:77:24: note: in expansion of macro 'INF'
   77 |             int val1 = INF, val2 = INF;
      |                        ^~~
travel.cpp:8:13: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+17' to '2147483647' [-Woverflow]
    8 | #define INF 1e17
      |             ^~~~
travel.cpp:77:36: note: in expansion of macro 'INF'
   77 |             int val1 = INF, val2 = INF;
      |                                    ^~~

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