oj.uz

Submission #1103756

# Submission time Handle Problem Language Result Execution time Memory
1103756 2024-10-21T15:49:35 Z vjudge1 Bitaro's travel (JOI23_travel) C++17
0 / 100
 2 ms 6736 KB 
#include <bits/stdc++.h>
using namespace std;

long long a[200005], ans[200005];
vector<long long> adj[200005];
stack<long long> st;

void dfs(long long x)
{
    for (auto y: adj[x])
    {
        ans[y]=ans[x]+abs(a[x]-a[y]);
        dfs(y);
    };
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, q, i, j, k;
    cin >> n;
    for (i=1; i<=n; i++)
    {
        cin >> a[i];
    };
    for (i=2; i<n; i++)
    {
        if (a[i]-a[i-1]<=a[i+1]-a[i])
        {
            while (!st.empty() && a[st.top()]-a[st.top()-1]<=a[i+1]-a[st.top()]) {st.pop();};
            if (st.empty()) {adj[1].push_back(i);}
            else {adj[st.top()].push_back(i);};
        }
        else {st.push(i);};
    };
    while (!st.empty()) {st.pop();};
    for (i=n-1; i>1; i--)
    {
        if (a[i]-a[i-1]>a[i+1]-a[i])
        {
            while (!st.empty() && a[st.top()+1]-a[st.top()]<a[st.top()]-a[i-1]) {st.pop();};
            if (st.empty()) {adj[n].push_back(i);}
            else {adj[st.top()].push_back(i);};
        }
        else {st.push(i);};
    };
    ans[1]=ans[n]=a[n]-a[1];
    dfs(1);
    dfs(n);
    cin >> q;
    while (q--)
    {
        cin >> i;
        j=upper_bound(a+1, a+n+1, i)-a-1;
        k=j+1;
        if (j==0) {cout << ans[k] << "\n";}
        else if (k==n+1) {cout << ans[j] << "\n";}
        else if (i-a[j]<=a[k]-i) {cout << ans[j] << "\n";}
        else {cout << ans[k] << "\n";};
    };
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 55.0

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