提出 #70624820

---

ソースコード 拡げる

#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 0
#endif
using namespace std;
using ll = long long;
using db = double;
const ll N = 1e6 + 5;
const ll md = 998244353;
const ll MOD = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db eps = 1e-6;
const db E = 2.718281828459045;
typedef pair<ll, ll> PLL;
#define fi first
#define se second
void solve()
{
    ll n;
    cin >> n;
    ll sum = 0;
    ll x;
    cin >> x;
    sum = 2 * x;
    set<ll> s1;
    set<ll, greater<ll>> s2;
    // map<ll, ll> unordered_map;
    s1.insert(0), s1.insert(x);
    s2.insert(0), s2.insert(x);
    cout << sum << '\n';
    for(ll i=2;i<=n;i++)
    {
        cin >> x;
        auto it =s1.upper_bound(x);
        ll z = 1e18;
        if(it!=s1.end())
        {
            ll k = *it;
            z = min(z, abs(k - x));
            ll zz = 1e18;
            auto itt1 = s1.upper_bound(k);
            if(itt1!=s1.end())
                zz = min(zz, abs(k - *itt1));
            auto itt2 = s2.upper_bound(k);
            if(itt2!=s2.end())
                zz = min(zz, abs(k - *itt2));
            if(zz>abs(k-x))
            {
                sum -= zz - abs(k - x);
            }
        }
        auto it2 = s2.upper_bound(x);
        if(it2!=s2.end())
        {
            ll k = *it2;
            z = min(z, abs(k - x));
            ll zz = 1e18;
            auto itt1 = s1.upper_bound(k);
            if(itt1!=s1.end())
                zz = min(zz, abs(k - *itt1));
            auto itt2 = s2.upper_bound(k);
            if(itt2!=s2.end())
                zz = min(zz, abs(k - *itt2));
            if(zz>abs(k-x))
            {
                sum -= zz - abs(k - x);
            }
        }
        sum += z;
        // unordered_map[x] = z;
        s1.insert(x), s2.insert(x);
        cout<<sum<<'\n';
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    T = 1;
    //cin>>T;
    while (T--)
    {
        solve();
    }
}

提出情報

ジャッジ結果