Submission #793159

#	Time	Username	Problem	Language	Result	Execution time	Memory
793159		phoenix	Bitaro's travel (JOI23_travel)	C++17	100 / 100	710 ms	61884 KiB

travel

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const ll INF = 1e18;
const int N = 2e5 + 10;

template<typename T>
struct SparseTable {
    int len;
    vector<vector<T>> st;
    T (*F) (T, T);
    void init(vector<T> &a, T (*f)(T, T)) {
        len = (int)a.size();
        F = f;
        int mxpw = 32 - __builtin_clz(len);
        st.resize(mxpw);
        st[0] = a;  
        for(int k = 1; k < mxpw; k++) {
            st[k].resize(len - (1 << k) + 1);
            for(int i = 0; i < (int)st[k].size(); i++) 
                st[k][i] = F(st[k - 1][i], st[k - 1][i + (1 << k - 1)]);
        }
    }
    T get(int l, int r) {
        assert(l >= 0 && r < len);
        int mxpw = 31 - __builtin_clz(r - l + 1);
        return F(st[mxpw][l], st[mxpw][r - (1 << mxpw) + 1]);
    }
};

SparseTable<ll> st_ld, st_rd;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin >> n;
    vector<ll> x(n + 2);
    x[0] = -INF; x[n + 1] = INF;

    for(int i = 1; i <= n; i++)
        cin >> x[i];
    vector<ll> b(n + 1);
    for(int i = 1; i <= n; i++) 
        b[i] = 2 * x[i + 1] - x[i];
    st_ld.init(b, [](ll a, ll b) {return (a > b ? a : b);});
    for(int i = 1; i <= n; i++) {
        b[i] = x[i] - 2 * x[i - 1];
    }
    st_rd.init(b, [](ll x, ll y) {return (x > y ? x : y);});
    int q;
    cin >> q;
    while(q --> 0) {
        int st;
        cin >> st;
        if(st <= x[1]) {
            cout << x[n] - st << '\n';
            continue;
        }
        if(st >= x[n]) {
            cout << st - x[1] << '\n';
            continue;
        }
        int lb, rb, bin_lb, bin_rb;
        bool turn = 0;
        bin_lb = 0, bin_rb = n + 1;
        while(bin_rb - bin_lb > 1) {
            int mid = (bin_rb + bin_lb) / 2;
            if(x[mid] < st) bin_lb = mid;
            else bin_rb = mid;
        }
        lb = bin_lb;
        bin_lb = 0, bin_rb = n + 1;
        while(bin_rb - bin_lb > 1) {
            int mid = (bin_rb + bin_lb) / 2;
            if(x[mid] > st) bin_rb = mid;
            else bin_lb = mid;
        }
        ll sum = 0;
        rb = bin_rb;
        sum += min(st - x[lb], x[rb] - st);
        if(st - x[lb] <= x[rb] - st) rb--;
        else lb++, turn = 1;
        // cout << lb << ' ' << rb << ' ' << sum << ' ' << turn << '\n';
        while(lb > 1 || rb < n) {
            if(!turn) {
                bin_lb = 0, bin_rb = lb;
                while(bin_rb - bin_lb > 1) {
                    int mid = (bin_lb + bin_rb) / 2;
                    if(st_ld.get(mid, lb - 1) <= x[rb + 1]) bin_rb = mid;
                    else bin_lb = mid;
                }
                sum += x[lb] - x[bin_rb];
                lb = bin_rb;
                if(rb < n) sum += x[++rb] - x[lb];
            } else {
                bin_lb = rb; bin_rb = n + 1;
                while(bin_rb - bin_lb > 1) {
                    int mid = (bin_rb + bin_lb) / 2;
                    if(st_rd.get(rb + 1, mid) < -x[lb - 1]) bin_lb = mid;
                    else bin_rb = mid;
                }
                sum += x[bin_lb] - x[rb];
                rb = bin_lb;
                if(lb > 1) sum += x[rb] - x[--lb];
            }
            // cout << lb << ' ' << rb << ' ' << sum << ' ' << turn << '\n';
            turn = !turn;
        }
        cout << sum << '\n';
    }
}

Compilation message (stderr)

travel.cpp: In instantiation of 'void SparseTable<T>::init(std::vector<_Tp>&, T (*)(T, T)) [with T = long long int]':
travel.cpp:48:59:   required from here
travel.cpp:23:66: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   23 |                 st[k][i] = F(st[k - 1][i], st[k - 1][i + (1 << k - 1)]);
      |                                                                ~~^~~

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