Submission #950319

#	Time	Username	Problem	Language	Result	Execution time	Memory
950319		andrei_boaca	Bitaro's travel (JOI23_travel)	C++17	100 / 100	304 ms	78420 KiB

travel

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll INF=1e17;
ll n,v[200005];
ll lft[200005],rgt[200005],rmqlft[21][200005],rmqrgt[21][200005],loga[200005];
bool finish(int l,int r)
{
    if(l==0&&r>=n)
        return 1;
    if(l<=1&&r==n+1)
        return 1;
    return 0;
}
ll getlft(ll l,ll r)
{
    int lg=loga[r-l+1];
    return max(rmqlft[lg][l],rmqlft[lg][r-(1<<lg)+1]);
}
ll getrgt(ll l,ll r)
{
    int lg=loga[r-l+1];
    return max(rmqrgt[lg][l],rmqrgt[lg][r-(1<<lg)+1]);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>v[i];
    for(int i=1;i<=n;i++)
    {
        if(i==1)
        {
            lft[i]=INF;
            continue;
        }
        lft[i]=(v[i]-v[i-1])-(v[n]-v[i]);
    }
    for(int i=n;i>=1;i--)
    {
        if(i==n)
        {
            rgt[i]=INF;
            continue;
        }
        rgt[i]=(v[i+1]-v[i])-(v[i]-v[1]);
    }
    for(int i=1;i<=n;i++)
    {
        rmqlft[0][i]=lft[i];
        rmqrgt[0][i]=rgt[i];
        for(int bit=0;bit<=20;bit++)
            if((1<<bit)<=i)
                loga[i]=bit;
    }
    for(int j=1;j<=18;j++)
        for(int i=1;i<=n;i++)
        {
            rmqlft[j][i]=rmqlft[j-1][i];
            rmqrgt[j][i]=rmqrgt[j-1][i];
            int poz=i+(1<<(j-1));
            if(poz<=n)
            {
                rmqlft[j][i]=max(rmqlft[j][i],rmqlft[j-1][poz]);
                rmqrgt[j][i]=max(rmqrgt[j][i],rmqrgt[j-1][poz]);
            }
        }
    ll q;
    cin>>q;
    while(q--)
    {
        ll x;
        cin>>x;
        ll ans=0;
        ll poz=0;
        ll st=1;
        ll dr=n;
        while(st<=dr)
        {
            ll mij=(st+dr)/2;
            if(v[mij]<=x)
            {
                poz=mij;
                st=mij+1;
            }
            else
                dr=mij-1;
        }
        if(poz==0)
        {
            ans=abs(v[1]-x);
            poz=1;
        }
        else if(poz==n)
            ans=abs(v[n]-x);
        else
        {
            ll dL=abs(v[poz]-x);
            ll dR=abs(v[poz+1]-x);
            if(dL<=dR)
                ans+=dL;
            else
            {
                ans=ans+dR;
                poz++;
            }
        }
        if(n==1)
        {
            cout<<ans<<'\n';
            continue;
        }
        int l=0,r=0;
        int dir=0; /// 0 -> left, 1 -> right
        if(poz==1)
        {
            ans+=abs(v[poz+1]-v[poz]);
            r=poz+1;
            l=poz-1;
            dir=1;
        }
        else if(poz==n)
        {
            ans+=abs(v[poz]-v[poz-1]);
            l=poz-1;
            r=poz+1;
            dir=0;
        }
        else
        {
            int dL=abs(v[poz]-v[poz-1]);
            int dR=abs(v[poz]-v[poz+1]);
            l=poz-1;
            r=poz+1;
            if(dL<=dR)
            {
                dir=0;
                ans+=dL;
            }
            else
            {
                dir=1;
                ans+=dR;
            }
        }
        while(!finish(l,r))
        {
            if(l==0)
            {
                ans+=v[n]-v[r];
                break;
            }
            if(r==n+1)
            {
                ans+=v[l]-v[1];
                break;
            }
            if(l==1&&r==n)
            {
                ans+=v[n]-v[1];
                break;
            }
            if(dir==0)
            {
                int last=l;
                int st=2;
                int dr=last;
                while(st<=dr)
                {
                    int mij=(st+dr)/2;
                    ll val=getlft(mij,l);
                    val+=(v[n]-v[r]);
                    if(val<=0)
                    {
                        last=mij-1;
                        dr=mij-1;
                    }
                    else
                        st=mij+1;
                }
                ans+=v[l]-v[last];
                l=last;
                ans+=v[r]-v[l];
                l--;
                dir^=1;
            }
            else
            {
                int last=r;
                int st=r;
                int dr=n-1;
                while(st<=dr)
                {
                    int mij=(st+dr)/2;
                    ll val=getrgt(r,mij);
                    val+=(v[l]-v[1]);
                    if(val<0)
                    {
                        last=mij+1;
                        st=mij+1;
                    }
                    else
                        dr=mij-1;
                }
                ans+=v[last]-v[r];
                r=last;
                ans+=v[r]-v[l];
                r++;
                dir^=1;
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}

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