提出 #72893517

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define rep(i, s, e) for (ll i = (ll)(s); i < (ll)(e); ++i)
#define rrep(i, s ,e) for (ll i = (ll)(s); i > (ll)(e); --i)
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
const ll MOD = 998244353;
//const ll MOD = 1000000007;

template <typename T>
struct SegmentTree {
private:
    int n;
    vector<T> node;
    T e = 0;//単位元
public:
    SegmentTree(vector<T> v) {
        ll sz = (ll)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1, e);

        for(ll i=0; i<sz; i++) node[i+n-1] = v[i];
        for(ll i=n-2; i>=0; i--) node[i] = merge(node[i*2+1],node[i*2+2]);
    }

    T merge(T a,T b){
        //
    }
    void update(ll k, T val) {
        k += (n - 1);
        node[k] = val;


        while(k > 0) {
            k = (k - 1) / 2;
            node[k] = merge(node[2*k+1],node[2*k+2]);
        }
    }

    T query(ll a, ll b, ll k=0, ll l=0, ll r=-1) {
        if(r < 0) r = n;
        if(b <= l || r <= a) return e;
        if(a <= l && r <= b) return node[k];

        T vl = query(a, b, 2*k+1, l, (l+r)/2);
        T vr = query(a, b, 2*k+2, (l+r)/2, r);
        return merge(vl,vr);
    }
 T operator[](ll at){
        at += n-1;
        return node[at];
    }


};


void solve(){
    ll ans = 0;
    ll n;cin >> n;
    vector<ll> v(n);
    vector<ll> c(n);
    rep(i,0,n)cin >> v[i];
    vector<pair<ll,ll>> a(n);
    rep(i,0,n)a[i] = {v[i],i};
    sort(a.begin(),a.end());
    set<ll> st;
    st.insert(-1);
    st.insert(INF);
    c[a[0].second] = a[0].first;
    st.insert(a[0].second);
    rep(i,1,n){
        auto[x,pos] = a[i];
        auto it = st.lower_bound(pos);
        auto it2 = it--;
        ll res = x;
        if(*it != INF){
            ll k = *it;
            res = min(res,c[k]+abs(pos-k));
        }
        if(*it2 != -1 && *it2 != INF){
          //cout << *it2 << endl;
            ll k = *it2;
            res = min(res,c[k]+abs(pos-k));
        }
        c[pos] = res;
        st.insert(pos);
    }
    rep(i,0,n)ans += (v[i]-c[i]);
    //for(auto x:c)cout << x << " ";
    cout << ans << endl;

}
int main(){
    cin.tie(0);cout.tie(0);
    ios_base::sync_with_stdio(false);
    
    ll t;cin >> t;
    while(t--){
        solve();
    }
}

提出情報

ジャッジ結果