oj.uz

Submission #1014791

# Submission time Handle Problem Language Result Execution time Memory
1014791 2024-07-05T14:32:33 Z alexdd Bitaro's travel (JOI23_travel) C++17
0 / 100
 3000 ms 7384 KB 
#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
    {
        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(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.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2480 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2460 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Execution timed out 3083 ms 7384 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

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