제출 #1014794

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

travel

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

int solve(int le, int ri, int poz)
{
    if(le==1 && ri==n)
        return 0;
    if(le>1 && (ri==n || poz-a[le-1] <= a[ri+1]-poz))///merge spre stanga
    {
        return solve(le-1,ri,a[le-1]) + poz-a[le-1];
        int st=2,dr=le,ans=le;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            if(qry(1,1,n,mij,le) <= 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
    {
        return solve(le,ri+1,a[ri+1]) + a[ri+1]-poz;
    }
}
///a[x]-a[x-1] <= a[ri]-a[x]
///2*a[x]-a[x-1] <= a[ri]
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: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 55