Submission #984887

#	Time	Username	Problem	Language	Result	Execution time	Memory
984887		vjudge2	Bitaro's travel (JOI23_travel)	C++17	100 / 100	424 ms	72364 KiB

travel

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

#define int long long
const int N = 200001;
const int lg = 19;

int lg2[N], mn[N][lg], mx[N][lg];

int query_min(int l, int r) {
    int j = lg2[r - l + 1];
    return min(mn[l][j], mn[r - (1 << j) + 1][j]);
}

int query_max(int l, int r) {
    int j = lg2[r - l + 1];
    return max(mx[l][j], mx[r - (1 << j) + 1][j]);
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, q;
    cin >> n;
    vector<int> x(n), ll(n), rr(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i];
        ll[i] = rr[i] = i;
    }
    for (int i = 1; i < n; i++) {
        int dist = x[i] - x[i - 1];
        int l = i, r = n - 1;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (x[mid] - x[i] < dist) l = mid;
            else r = mid - 1;
        }
        if (x[l] - x[i] < dist) rr[i - 1] = l; // if i'm going left to i - 1, rb must > l
    }
    for (int i = 0; i < n - 1; i++) {
        int dist = x[i + 1] - x[i];
        int l = 0, r = i;
        while (l < r) {
            int mid = (l + r) / 2;
            if (x[i] - x[mid] <= dist) r = mid;
            else l = mid + 1;
        }
        if (x[i] - x[l] <= dist) ll[i + 1] = l; // if i'm going right to i + 1, lb must < l
    }
    // for (int i = 0; i < n; i++) cout << ll[i] << ' ' << rr[i] << '\n';
    // lg2[1] = 0;
    for (int i = 2; i <= n; i++) lg2[i] = lg2[i / 2] + 1;
    for (int i = 0; i < n; i++) mx[i][0] = rr[i], mn[i][0] = ll[i];
    for (int j = 1; j < lg; j++) {
        for (int i = 0; i + (1 << j) - 1 < n; i++) {
            mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
            mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
        }
    }
    cin >> q;
    while (q--) {
        int s, ans = 0;
        cin >> s;
        int left = 0, lb, rb, cp;
        if (s >= x.back()) left = 1, lb = rb = n - 1, ans += s - x.back(), cp = n - 1;
        else if (s > x.front()) {
            auto it = lower_bound(x.begin(), x.end(), s);
            int prv, nxt;
            if ((*it) == s) {
                prv = *prev(it);
                nxt = *next(it);
                lb = rb = cp = it - x.begin();
            } else {
                prv = *prev(it);
                nxt = *it;
                if (s - prv <= nxt - s) lb = rb = cp = it - x.begin() - 1, ans += s - prv;
                else lb = rb = cp = it - x.begin(), ans += nxt - s;
            }
            if (lb == 0) left = 1;
            else if (rb == n - 1) left = 0;
            else {
                prv = x[lb - 1];
                nxt = x[rb + 1];
                if (x[cp] - prv <= nxt - x[cp]) left = 0;
                else left = 1;
            }
        } else lb = rb = 0, ans += x.front() - s, cp = 0;
        // cout << "ans:" << lb << ' ' << rb << ' ' << ans << '\n';
        for (int ti = 0; ti < (lg << 1); ti++) {
            left ^= 1;
            if (lb <= 0 && rb > n) break;
            if (left && lb > 0) {
                int l = 0, r = lb - 1;
                while (l < r) {
                    int mid = (l + r) / 2;
                    if (rb >= query_max(mid, lb - 1)) r = mid;
                    else l = mid + 1;
                }
                ans += abs(x[cp] - x[l]);
                lb = cp = l;
                // cout << "ans:" << lb << ' ' << rb << ' ' << ans << '\n';
            } else if (!left && rb < n - 1) {
                int l = rb + 1, r = n - 1;
                while (l < r) {
                    int mid = (l + r + 1) / 2;
                    if (lb <= query_min(rb + 1, mid)) l = mid;
                    else r = mid - 1;
                }
                ans += abs(x[l] - x[cp]);
                rb = cp = l;
                // cout << "ans:" << lb << ' ' << rb << ' ' << ans << '\n';
            }
            // cout << "iter\n";
        }
        // cout << "final ans:" << lb << ' ' << rb << ' ' << ans << '\n';
        cout << ans << '\n';
    }
}

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