Submission #890886

#	Time	Username	Problem	Language	Result	Execution time	Memory
890886		vjudge1	Bitaro's travel (JOI23_travel)	C++17	30 / 100	109 ms	8528 KiB

travel

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    vector <int> X(n);
    for ( auto &u: X ) cin >> u;
    int q; cin >> q;
    vector <int> S(q);
    for ( auto &u: S ) cin >> u;
    if ( 0 && q == 1 ){
        int x = S[0];
        const int inf = 1e15;
        set <int> st{-inf, inf};
        for ( int i = 0; i < n; i++ ){
            st.insert(X[i]);
        }
        int ans = 0;
        while ( st.size() > 2 ){
            auto it = st.lower_bound(x);
            assert(*prev(it) <= x && *it >= x);
            if ( abs(*prev(it) - x) <= abs(*it - x) ){
                ans += x - *prev(it);
                x = *prev(it);
                st.erase(prev(it));
            } else{
                ans += -x + *it;
                x = *it;
                st.erase(it);
            }
        }
        cout << ans << ln;
        return 0;
    }
    for ( auto &xx: S ){
        int it = lower_bound(all(X), xx) - X.begin();
        if ( it - 1 >= 0 && (it == n || X[it] - xx >= xx - X[it - 1]) ) --it;
        int ans = abs(X[it] - xx), l = it - 1, r = it + 1, x = X[it];
        while ( l >= 0 || r < n ){
//            cout << l + 1 << " " << r + 1 << " -> " << x << ", " << ans << ln;
            if ( l < 0 ){
                ans += abs(X.back() - x);
                break;
            } else if ( r >= n ){
                ans += abs(X[0] - x);
                break;
            } else{
                if ( abs(X[r] - x) >= 100 && abs(X[l] - x) <= 100 ){
                    ans += abs(X[0] - x);
                    x = X[0]; l = -1;
                    continue;
                }
                if ( abs(X[l] - x) > 100  ){
                    ans += abs(X.back() - x);
                    x = X.back(); r = n;
                    continue;
                }
                if ( abs(X[l] - x) <= abs(X[r] - x) ){
                    ans += abs(X[l] - x);
                    x = X[l--];
                } else{
                    ans += abs(X[r] - x);
                    x = X[r++];
                }
            }
        }
        cout << ans << ln;
    }

    cout << '\n';
}

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