Submission #1014807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014807		alexdd	Bitaro's travel (JOI23_travel)	C++17	15 / 100	3096 ms	12112 KiB

travel

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a[200005];
int aint[530005][2];
void build(int nod, int st, int dr)
{
    if(st==dr)
    {
        aint[nod][0] = 2*a[st]-a[st-1];
        aint[nod][1] = a[st]-2*a[st-1];
        return;
    }
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
    aint[nod][0] = max(aint[nod*2][0], aint[nod*2+1][0]);
    aint[nod][1] = max(aint[nod*2][1], aint[nod*2+1][1]);
}
int qry(int nod, int st, int dr, int le, int ri, int c)
{
    if(le>ri)
        return -1;
    if(le==st && dr==ri)
        return aint[nod][c];
    int mij=(st+dr)/2;
    return max(qry(nod*2,st,mij,le,min(mij,ri),c),
               qry(nod*2+1,mij+1,dr,max(mij+1,le),ri,c));
}

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(1,1,n,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(1,1,n,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];
    }
    build(1,1,n);
    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: 0 / 30
• Subtask 4: 0 / 55