Submission #1103902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103902		lampooppp	Bitaro's travel (JOI23_travel)	C++17	100 / 100	452 ms	8044 KiB

travel

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

const int N=2e5;
int a[N+1];
int n,q;


int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
//    freopen("ex_interval3.in", "r", stdin);
    cin >> n;
    for(int i=1;i<=n;++i) cin >> a[i];
    cin >> q;
    while(q--)
    {
        int x;
        cin >> x;
        int id = lower_bound(a+1,a+n+1,x)-a;
        int sum=0;
        if(id==1)
        {
            cout << a[n]-x << '\n';
            continue;
        }
        if(id==n+1)
        {
            cout << x-a[1] << '\n';
            continue;
        }
        int l=id-1;
        int r=id;
        int now;
        if(x-a[l]<=a[r]-x)
        {
            now=0;
            r=l;
            sum=x-a[l];
        }
        else
        {
            now=1;
            l=r;
            sum=a[r]-x;
        }
        bool done=false;
        while(l>1 || r<n)
        {
            if(r==n || l==1)
            {
                cout << sum+(a[n]-a[1]) << '\n';
                done=true;
                break;
            }
            if(now==0)
            {
                int x = a[l]-a[l-1];
                int id = lower_bound(a+r+1,a+n+1,a[l]+x)-a-1;
                if(id==r) {
                    int x =a[r+1]-a[l];
                    int id2 = lower_bound(a+1,a+l,a[l]-x)-a;
                    sum+=a[l]-a[id2];
                    l=id2;
                }
                else
                {
                    sum+=a[id]-a[l];
                    r=id;
                    now=1;
                }
            }
            else
            {
                int x = a[r+1]-a[r];
                int id = lower_bound(a+1,a+l,a[r]-x)-a;
                if(id==l) {
                    int x = a[r]-a[l-1];
                    int id2 = lower_bound(a+r+1,a+n+1,a[r]+x)-a-1;
                    sum+=a[id2]-a[r];
                    r=id2;
                }
                else
                {
                    sum+=a[r]-a[id];
                    l=id;
                    now=0;
                }
            }
        }

    }

}

//9 4
//2 5
//1 7
//6 7
//1 4
//3 5
//0 8
//1 7
//1 2
//9 10

Compilation message (stderr)

travel.cpp: In function 'int32_t main()':
travel.cpp:49:14: warning: variable 'done' set but not used [-Wunused-but-set-variable]
   49 |         bool done=false;
      |              ^~~~

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