Submission #729017

#	Time	Username	Problem	Language	Result	Execution time	Memory
729017		MilosMilutinovic	Bitaro's travel (JOI23_travel)	C++14	100 / 100	483 ms	46972 KiB

travel

#include <bits/stdc++.h>
using namespace std;
 
int n,x[200005],q,mxl[200005][25],mxr[200005][25],logs[200005];
 
int findbst(int s)
{
    int idx=lower_bound(x+1,x+n+1,s)-x;
    idx=max(idx,1);idx=min(idx,n);
    if(abs(x[idx]-s)<abs(x[max(idx-1,1)]-s)) return idx;
    else return max(idx-1,1);
}
 
int getL(int l,int r)
{
    int k=logs[r-l+1];
    return max(mxl[l][k],mxl[r-(1<<k)+1][k]);
}
int getR(int l,int r)
{
    int k=logs[r-l+1];
    return max(mxr[l][k],mxr[r-(1<<k)+1][k]);
}
 
signed main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&x[i]);
    for(int i=2;i<=n;i++) logs[i]=logs[i>>1]+1;
    for(int i=2;i<=n;i++) mxl[i][0]=2*x[i]-x[i-1];
    for(int i=1;i<n;i++) mxr[i][0]=x[i+1]-2*x[i];
    for(int j=1;j<25;j++)
        for(int i=2;i+(1<<j)<=n+1;i++)
            mxl[i][j]=max(mxl[i][j-1],mxl[i+(1<<(j-1))][j-1]);
    for(int j=1;j<25;j++)
        for(int i=1;i+(1<<j)<=n;i++)
            mxr[i][j]=max(mxr[i][j-1],mxr[i+(1<<(j-1))][j-1]);
    scanf("%d",&q);
    while(q--)
    {
        int s;scanf("%d",&s);
        int l=findbst(s),r=l,idx=l;
        long long ans=abs(s-x[l]);
        while(l!=1||r!=n)
        {
            if(l==1)
            {
                ans+=abs(x[idx]-x[n]);r=n;break;
            }
            if(r==n)
            {
                ans+=abs(x[1]-x[idx]);l=1;break;
            }
            if(l==idx)
            {
                int low=2,high=l,p=l;
                while(low<=high)
                {
                    int mid=(low+high)/2;
                    if(getL(mid,l)-x[r+1]<=0) p=mid-1,high=mid-1;
                    else low=mid+1;
                }
                ans+=x[l]-x[p];l=p;
                ans+=x[r+1]-x[p];idx=r+1;r=idx;
            }
            else
            {
                assert(r==idx);
                int low=r,high=n-1,p=r;
                while(low<=high)
                {
                    int mid=(low+high)/2;
                    if(getR(r,mid)+x[l-1]<0) p=mid+1,low=mid+1;
                    else high=mid-1;
                }
                ans+=x[p]-x[r];r=p;
                ans+=x[p]-x[l-1];idx=l-1;l=idx;
            }
        }
        printf("%lld\n",ans);
    }
}

Compilation message (stderr)

travel.cpp: In function 'int main()':
travel.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
travel.cpp:28:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     for(int i=1;i<=n;i++)scanf("%d",&x[i]);
      |                          ~~~~~^~~~~~~~~~~~
travel.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
travel.cpp:41:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         int s;scanf("%d",&s);
      |               ~~~~~^~~~~~~~~

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