Submission #784430

#	Time	Username	Problem	Language	Result	Execution time	Memory
784430		12345678	Bitaro's travel (JOI23_travel)	C++17	100 / 100	199 ms	12988 KiB

travel

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=2e5+5;
int n, v[nx], q, s, l, r, dr[nx], dl[nx];
long long ans;
bool isl;

struct rsegtree
{
    int d[4*nx];
    void build(int l, int r, int i)
    {
        if (l==r) return void(d[i]=dr[l]);
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=min(d[2*i], d[2*i+1]);
    }
    int query(int l, int r, int i, int ql, int qr, int vl)
    {
        if (qr<l||r<ql) return -1;
        if (ql<=l&&r<=qr&&vl<d[i]) return -1;
        if (l==r) return l;
        int md=(l+r)/2, tmp=query(l, md, 2*i, ql, qr, vl);
        if (tmp!=-1) return tmp;
        return query(md+1, r, 2*i+1, ql, qr, vl);
    }
} rs;

struct lsegtree
{
    int d[4*nx];
    void build(int l, int r, int i)
    {
        if (l==r) return void(d[i]=dl[l]);
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    int query(int l, int r, int i, int ql, int qr, int vl)
    {
        if (qr<l||r<ql) return -1;
        if (ql<=l&&r<=qr&&vl>=d[i]) return -1;
        if (l==r) return l;
        int md=(l+r)/2, tmp=query(md+1, r, 2*i+1, ql, qr, vl);
        if (tmp!=-1) return tmp;
        return query(l, md, 2*i, ql, qr, vl);
    }
} ls;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    v[0]=-1e9; v[n+1]=2e9;
    for (int i=1; i<=n; i++) cin>>v[i];
    for (int i=1; i<=n; i++) dr[i]=2*v[i]-v[i+1];
    for (int i=1; i<=n; i++) dl[i]=2*v[i]-v[i-1];
    rs.build(1, n, 1);
    ls.build(1, n, 1);
    cin>>q;
    while (q--)
    {
        cin>>s;
        int cl=lower_bound(v+1, v+n+1, s)-v;
        if (s-v[cl-1]<=v[cl]-s) l=r=cl-1, ans=s-v[cl-1];
        else l=r=cl, ans=v[cl]-s;
        isl=1;
        while (l!=1&&r!=n)
        {
            if (isl&&l!=1)
            {
                int np=ls.query(1, n, 1, 1, l, v[r+1]);
                ans+=v[r]-v[np];
                l=np;
            }
            if (!isl&&r!=n)
            {
                int np=rs.query(1, n, 1, r, n, v[l-1]);
                ans+=v[np]-v[l];
                r=np;
            }
            isl=!isl;
        }
        //cout<<l<<' '<<r<<' '<<ans<<'\n';
        if (r==n) ans+=v[r]-v[1];
        else ans+=v[n]-v[l];
        cout<<ans<<'\n';
    }
}

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