제출 #1237040

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1237040		rythm_of_knight	Bitaro's travel (JOI23_travel)	C++17	0 / 100	186 ms	4072 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] = -1e9 - 4;
    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 (1 < tl || tr < n) {
            int l = 0, r = tl;
            while (l + 1 < r) {
                int m = l + r >> 1;
                if (x[cur] - x[m] <= x[tr + 1] - x[cur])
                    r = m;
                else
                    l = m;
            }
            if (r < tl) {
                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[cur] - x[tl - 1])
                    l = m;
                else
                    r = m;
            }
            if (l > tr) {
                res += x[l] - x[cur];
                tr = cur = l;
            }
        }
        ans[i] = res;
    }
    int q;
    cin >> q;
    while (q--) {
        int s;
        cin >> s;
        int i = lower_bound(all(x), s) - x.begin();
        ll res = 1e18;
        if (i <= n)
            res = min(res, ans[i] + x[i] - s);
        if (i > 1)
            res = min(res, ans[i - 1] + s - x[i - 1]);
        cout << res << '\n';
    }
}

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