Submission #979020

#	Time	Username	Problem	Language	Result	Execution time	Memory
979020		abc864197532	Bitaro's travel (JOI23_travel)	C++17	100 / 100	182 ms	22172 KiB

travel

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
#define pii pair<int,int>
#define sz(a) (int(a.size()))
const int N = 105;

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    cin >> n;
    vector <int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    if (n == 1) {
        int q;
        cin >> q;
        while (q--) {
            int x;
            cin >> x;
            cout << abs(a[0] - x) << '\n';
        }
        return 0;
    }
    vector <int> ptl(n), ptr(n);
    {
        vector <pair <int, int>> event;
        for (int i = 1; i + 1 < n; ++i) {
            event.emplace_back(2 * a[i] - a[i - 1], -i);
            event.emplace_back(a[i + 1], i);
        }
        sort(all(event)), reverse(all(event));
        set <int> S;
        for (auto [x, y] : event) {
            if (y > 0) {
                auto it = S.upper_bound(y);
                if (it != S.begin()) {
                    ptl[y] = *prev(it);
                }
            } else {
                S.insert(-y);
            }
        }
    }
    {
        vector <pair <int, int>> event;
        for (int i = 1; i + 1 < n; ++i) {
            event.emplace_back(2 * a[i] - a[i + 1], -i);
            event.emplace_back(a[i - 1], i);
        }
        sort(all(event));
        set <int> S;
        for (auto [x, y] : event) {
            if (y > 0) {
                auto it = S.lower_bound(y);
                if (it != S.end()) {
                    ptr[y] = *it;
                } else {
                    ptr[y] = n - 1;
                }
            } else {
                S.insert(-y);
            }
        }
    }
    vector <ll> ans(n);
    for (int st = 0; st < n; ++st) {
        int l = st, r = st;
        int left = st == n - 1 || (st && a[st] - a[st - 1] <= a[st + 1] - a[st]);
        while (l > 0 || r + 1 < n) {
            if (l == 0 || r + 1 == n) {
                ans[st] += a[n - 1] - a[0];
                break;
            }
            if (left) {
                // find max i s.t. 2a_i > a{r + 1} + a_{i - 1}
                int now = ptl[r];
                // while (now && 2 * a[now] <= a[r + 1] + a[now - 1]) {
                //     now--;
                // }
                if (!now) {
                    ans[st] += (a[l] - a[now]);
                    l = now;
                } else {
                    ans[st] += (a[l] - a[now]) + (a[r + 1] - a[now]);
                    left ^= 1;
                    l = now, r++;
                }
            } else {
                // find min i s.t. 2a_i <= a_{l - 1} + a_{i + 1} 
                int now = ptr[l];
                // while (now + 1 < n && 2 * a[now] > a[l - 1] + a[now + 1]) {
                //     now++;
                // }
                if (now == n - 1) {
                    ans[st] += (a[now] - a[r]);
                    r = now;
                } else {
                    ans[st] += (a[now] - a[r]) + (a[now] - a[l - 1]);
                    left ^= 1;
                    l--, r = now;
                }
            }
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        int p = lower_bound(all(a), x) - a.begin();
        if (p < n && a[p] == x) {
            cout << ans[p] << '\n';
        } else {
            int q = p - 1;
            if (q == -1) {
                cout << ans[p] + abs(x - a[p]) << '\n';
            } else if (p == n) {
                cout << ans[q] + abs(x - a[q]) << '\n';
            } else if (x - a[q] <= a[p] - x) {
                cout << ans[q] + abs(x - a[q]) << '\n';
            } else {
                cout << ans[p] + abs(x - a[p]) << '\n';
            }
        }
    }
}

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