Submission #888583

#	Time	Username	Problem	Language	Result	Execution time	Memory
888583		box	Bitaro's travel (JOI23_travel)	C++17	100 / 100	402 ms	7432 KiB

travel

#include <bits/stdc++.h>
using namespace std;

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;

const int N = 2e5;

int n, q, x[N];

i64 rec(int l, int r, bool dir) {
    int p = x[dir ? r : l];
    if (l == 0) return x[n - 1] - p;
    if (r == n - 1) return p - x[0];
    if (p - x[l - 1] <= x[r + 1] - p) {
        int q = lower_bound(x, x + n, 2 * p - x[r + 1]) - x;
        return p - x[q] + rec(q, r, 0);
    } else {
        int q = upper_bound(x, x + n, 2 * p - x[l - 1]) - x - 1;
        return x[q] - p + rec(l, q, 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> x[i];
    cin >> q;
    while (q--) {
        int s;
        cin >> s;
        int p = upper_bound(x, x + n, s) - x - 1;
        if (p == -1) cout << x[n - 1] - s << '\n';
        else if (p == n - 1) cout << s - x[0] << '\n';
        else if (s - x[p] <= x[p + 1] - s) cout << s - x[p] + rec(p, p, 0) << '\n';
        else cout << x[p + 1] - s + rec(p + 1, p + 1, 1) << '\n';
    }

}

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