Submission #70668583

---

Source Code Expand

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

int main(){
    int n;
    cin >> n;

    ll inf = 1e17;
    map<ll, ll> Dist;
    Dist[0] = inf;
    ll ans = inf;
    while(n--){
        ll x;
        cin >> x;
        
        auto next = Dist.lower_bound(x);
        auto prev = next; prev--;

        // cout << "prev " << (*prev).first << " " << (*prev).second << endl;
        // cout << "next " << (*next).first << " " << (*next).second << endl;

        if(next == Dist.end()){
            ll d_prev = x - (*prev).first;

            ans += d_prev;
            Dist[x] = d_prev;

            if(d_prev < (*prev).second){
                ans -= (*prev).second;
                ans += d_prev;
                Dist[(*prev).first] = d_prev;
            } 
        }else{
            ll d_prev = x - (*prev).first;
            ll d_next = (*next).first - x;

            ans += min(d_prev, d_next);
            Dist[x] = min(d_prev, d_next);

            if(d_prev < (*prev).second){
                ans -= (*prev).second;
                ans += d_prev;
                Dist[(*prev).first] = d_prev;
            }

            if(d_next < (*next).second){
                ans -= (*next).second;
                ans += d_next;
                Dist[(*next).first] = d_next;
            }
        }

        // for(auto [key, value] : Dist) cout << key << " " << value << endl;
        cout << ans << endl;
        // cout << endl;
        
    }
}

Submission Info

Judge Result