Submission #1237012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237012		rythm_of_knight	Bitaro's travel (JOI23_travel)	C++17	In queue	0 ms	0 KiB

travel

#include <bits/stdc++.h>
#define ar array
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector <int> x(n + 2);
    x[n + 1] = 2e9 + 4; x[0] = -x[n + 1];
    for (int i = 1; i <= n; i++)
        cin >> x[i];
    vector <ll> ans(n + 2, 1e18);
    for (int i = 1; i <= n; i++) {
        ll res = 0;
        int tl = i, tr = i, cur = i;
        while (tl != 1 || tr != n) {
            int cnt = 0;
            int l = 0, r = tl;
            while (l + 1 < r) {
                int m = l + r >> 1;
                if (x[cur] - x[m] <= x[tr + 1] - x[tr])
                    r = m;
                else
                    l = m;
            }
            if (r < tl) {
                cnt++;
                res += x[cur] - x[r];
                tl = cur = r;
            }
            l = tr, r = n + 1;
            while (l + 1 < r) {
                int m = l + r >> 1;
                if (x[m] - x[cur] < x[tl] - x[tl - 1])
                    l = m;
                else
                    r = m;
            }
            if (l > tr) {
                cnt++;
                res += x[l] - x[cur];
                tr = cur = l;
            }
            // cout << tl << ' '  << tr << '\n';
            if (!cnt && tl > 1 && tr < n)
                return 0;
        }
        ans[i] = res;
    }
    int q;
    cin >> q;
    while (q--) {
        int s;
        cin >> s;
        int i = lower_bound(all(x), s) - x.begin();
        cout << min(ans[i - 1] + s - x[i - 1], ans[i] + x[i] - s) << '\n';
    }
}