提出 #70707927

---

ソースコード 拡げる

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

constexpr int INF = 2002002002;

/////////////////// メイン ///////////////////

int main () {
  
  /////////////////// 前入力 ///////////////////
  
  int n;
  cin >> n;

  /////////////////// 前処理 ///////////////////

  // めっちゃ右とめっちゃ左（1e9以上離れた場所）で1人ずつ番兵をおく
  // 番兵の外側は自分自身としておくことで、番兵の距離が計算上常に0となる

  // 位置を記録
  vector<int> vx(n+3,0);

  // 自分の左右にいるメンバーを記録
  vector<int> vl(n+3,-1);
  vector<int> vr(n+3,-1);

  // 左右の距離の最小値
  vector<int> vd(n+3,0);

  // 初期状態（番兵2人）のデータを作る（0番はあとで追加する）
  vx.at(n+1) = -INF;
  vl.at(n+1) = n+1;
  vr.at(n+1) = n+2;
  vd.at(n+1) = 0;
  vx.at(n+2) = INF;
  vl.at(n+2) = n+1;
  vr.at(n+2) = n+2;
  vd.at(n+2) = 0;

  // メンバーの位置を検索する用のset
  set <pair<int,int>> st;
  st.emplace(-INF,n+1);
  st.emplace(INF,n+2);

  //////////////// 出力変数定義 ////////////////

  int result = 0;

  /////////////////// ループ ///////////////////

  // 0番から自分で入れる
  for (int i=0; i<=n; i++) {
    
    //////////////////// 入力 ////////////////////

    int x;
    if (i==0) x = 0;
    else cin >> x;

    //////////////// 出力変数定義 ////////////////



    //////////////////// 処理 ////////////////////

    // 位置を記録
    vx.at(i) = x;

    // 左右メンバーを検索してから、検索用データを更新
    auto it = st.upper_bound({x,0});
    int r = (*it).second;
    it--;
    int l = (*it).second;
    st.emplace(x,i);

    // 左右メンバーのデータを合計から一時削除
    result -= vd.at(l);
    result -= vd.at(r);

    // 左右関係を更新
    vr.at(l) = i;
    vl.at(i) = l;
    vl.at(r) = i;
    vr.at(i) = r;

    // 本人と左右について、距離情報を更新して合計に加算
    vector<int> tmp = {l,i,r};
    for (int j : tmp) {

      vd.at(j) = min(vx.at(j)-vx.at(vl.at(j)),vx.at(vr.at(j))-vx.at(j));
      result += vd.at(j);

    }

    //////////////////// 出力 ////////////////////

    if (i!=0) cout << result << endl;
    
  }

  /////////////////// 後処理 ///////////////////



  //////////////////// 終了 ////////////////////

  return 0;

}

提出情報

ジャッジ結果