oj.uz

Submission #784428

# Submission time Handle Problem Language Result Execution time Memory
784428 2023-07-16T06:16:42 Z 12345678 Bitaro's travel (JOI23_travel) C++17
0 / 100
 1 ms 340 KB 
#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, ans=s-v[cl-1];
        else l=r=cl, ans=v[cl]-s;
        isl=1;
        int cnt=0;
        while (l!=1&&r!=n&&++cnt!=5)
        {
            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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -