Submission #915290

#	Time	Username	Problem	Language	Result	Execution time	Memory
915290		LOLOLO	Bitaro's travel (JOI23_travel)	C++17	100 / 100	1391 ms	41032 KiB

travel

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

#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 2e5 + 100;
ll p[N], dis[N];
ll sp[N][20], n;

void build() {
    for (int i = 2; i <= n; i++) {
        dis[i] = p[i] - p[i - 1];
        sp[i][0] = dis[i];
    }

    for (int j = 1; j < 20; j++) {
        for (int i = 1; i + (1 << j) <= n + 1; i++) {
            sp[i][j] = max(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int get(int l, int r) {
    l++;
    if (l > r)
        return -1;

    int t = log2(r - l + 1);
    return max(sp[l][t], sp[r - (1 << t) + 1][t]);
}

ll get(int l, int r, int x) {
    ll ans = 0;
    while (l >= 1 || r <= n) {
        if (r > n) {
            ans += abs(x - p[1]);
            break;
        }

        if (l < 1) {
            ans += abs(x - p[n]);
            break;
        }

        ll dis = max(abs(p[r] - x), abs(p[l] - x));
        if (abs(p[l] - x) <= abs(p[r] - x)) {
            int nw = 0, l1 = 1, r1 = l;
            while (l1 <= r1) {
                int m = (l1 + r1) / 2;
                if (get(m, l) <= dis) {
                    nw = m;
                    r1 = m - 1;
                } else {
                    l1 = m + 1;
                }
            }
            ans += abs(x - p[nw]);
            x = p[nw];
            l = nw - 1;
        } else {
            int nw = 0, l1 = r, r1 = n;
            while (l1 <= r1) {
                int m = (l1 + r1) / 2;
                if (get(r, m) < dis) {
                    nw = m;
                    l1 = m + 1;
                } else {
                    r1 = m - 1;
                }
            }
            ans += abs(x - p[nw]);
            x = p[nw];
            r = nw + 1;
        }
    }

    return ans;
}

ll solve() {
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }


    build();

    int q;
    cin >> q;

    for (int i = 1; i <= q; i++) {
        ll x;
        cin >> x;
        int r = lower_bound(p + 1, p + 1 + n, x) - p, l = r - 1;
        cout << get(l, r, x) << '\n';
    }

    return 0;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;

    while (t--) {
        solve();
        //cout << solve() << '\n';
    }

    return 0;
}

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