Submission #792453

#	Time	Username	Problem	Language	Result	Execution time	Memory
792453		vjudge1	Bitaro's travel (JOI23_travel)	C++17	15 / 100	3078 ms	36692 KiB

travel

#include <bits/stdc++.h>

#define fi first
#define se second

const int N = 200200;

using namespace std;

int n;
long long a[N];
long long t[N][20];
long long L[N];

long long get(int l, int r)
{
    int g = L[r - l + 1];
    return max(t[l][g], t[r - (1 << g) + 1][g]);
}

long long go_one(int &l, int&r, int &k)
{
    if (l == 1 && r == n) {
        return 0;
    }
    long long res;
    if (abs(a[k] - a[l - 1]) <= abs(a[k] - a[r + 1])) {
        l--;
        res = abs(a[k] - a[l]);
        k = l;
    } else {
        r++;
        res = abs(a[k] - a[r]);
        k = r;
    }
    return res;
}

long long solve(int k)
{
    int l = k, r = k;
    long long res = go_one(l, r, k);
    while (l > 1 || r < n) {

        res += go_one(l, r, k);
    }
    return res;
}

int main()
{
    #ifdef zxc
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    a[0] = -2e9;
    a[n + 1] = 2e9;

    for (int i = 1; i <= n; i++) {
        t[i][0] = a[i + 1] - a[i];
    }
    for (int i = 2; i < N; i++) {
        L[i] = L[i / 2] + 1;
    }
    for (int i = 1; i < 20; i++) {
        for (int j = 1; j + (1 << i) - 1 <= n; j++) {
            t[j][i] = max(t[j][i - 1], t[j + (1 << i)][i - 1]);
        }
    }

    int q;
    cin >> q;
    while (q--) {
        long long x;
        cin >> x;
        int i = lower_bound(a + 1, a + n + 1, x) - a;
        if (i > 1 && abs(a[i - 1] - x) <= abs(a[i] - x)) {
            i--;
        }

        cout << solve(i) + abs(a[i] - x) << "\n";
    }
}

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