제출 #1014850

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

travel

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

/*ifstream fin("input.in");
ofstream fout("output.out");
#define cin fin
#define cout fout*/

#define int long long
int n;
int a[200005];
int rmq[2][18][200005];
int p2[200005];
int qry(int le, int ri, int c)
{
    int p = p2[ri-le+1];
    return max(rmq[c][p][le], rmq[c][p][ri-(1<<p)+1]);
}
int solve(int le, int ri, int poz)
{
    if(le==1 && ri==n)
        return 0;
    if(le==1)
    {
        return a[n]-poz;
    }
    else if(ri==n)
    {
        return poz-a[1];
    }
    if(le>1 && (ri==n || poz-a[le-1] <= a[ri+1]-poz))///merge spre stanga
    {
        int st=2,dr=le,ans=le;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            if(qry(mij,le,0) <= a[ri+1])
            {
                ans=mij;
                dr=mij-1;
            }
            else
                st=mij+1;
        }
        return solve(ans-1,ri,a[ans-1]) + poz-a[ans-1];
    }
    else///merge spre dreapta
    {
        int st=ri+1,dr=n,ans=ri+1;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            if(qry(ri+1,mij,1) < -a[le-1])
            {
                ans=mij;
                st=mij+1;
            }
            else
                dr=mij-1;
        }
        return solve(le,ans,a[ans]) + a[ans]-poz;
    }
}
///a[x]-a[x-1] <= a[ri]-a[x]
///2*a[x]-a[x-1] <= a[ri]
///a[x]-a[x-1] <= a[x-1] - a[le]
///a[x]-2*a[x-1] <= -a[le]
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        rmq[0][0][i] = 2*a[i]-a[i-1];
        rmq[1][0][i] = a[i]-2*a[i-1];
    }
    for(int p=1;p<18;p++)
    {
        for(int i=1;i+(1<<p)-1<=n;i++)
        {
            rmq[0][p][i] = max(rmq[0][p-1][i], rmq[0][p-1][i+(1<<(p-1))]);
            rmq[1][p][i] = max(rmq[1][p-1][i], rmq[1][p-1][i+(1<<(p-1))]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        p2[i]=0;
        while(p2[i]+1<18 && (1<<(p2[i]+1))<=i)
            p2[i]++;
    }

    int q,s;
    cin>>q;
    while(q--)
    {
        cin>>s;
        if(s<=a[1])
            cout<<solve(1,1,a[1])+(a[1]-s)<<"\n";
        else if(s>=a[n])
            cout<<solve(n,n,a[n])+(s-a[n])<<"\n";
        else
        {
            int st=1,dr=n-1,ans=n;
            while(st<=dr)
            {
                int mij=(st+dr)/2;
                if(a[mij]>=s)
                {
                    ans=mij;
                    dr=mij-1;
                }
                else
                    st=mij+1;
            }
            if(ans==1 || a[ans]-s < s-a[ans-1]) cout<<solve(ans,ans,a[ans])+(a[ans]-s)<<"\n";
            else cout<<solve(ans-1,ans-1,a[ans-1])+(s-a[ans-1])<<"\n";
        }
    }
    return 0;
}

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