提出 #7576185

---

ソースコード 拡げる

#include <bits/stdc++.h>

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

signed main() {
  ll N;
  cin >> N;
  vector<ll> t(N+1); // t[val] = index
  rep(i, N) {
    ll x;
    cin >> x;
    t[x] = i+1;
  }

  ll ans = 0;
  set<ll> s;
  for (ll val=N; val>=1; val--) {
    {
      // 右側に最大値がある場合
      ll j, i1, i2;
      auto it = s.lower_bound(t[val]);
      if (it == s.end())
        goto END1;
      i1 = *it;
      it++;
      if (it == s.end())
        i2 = N+1;
      else
        i2 = *it;

      it = s.lower_bound(t[val]);
      if (it == s.begin()) {
        j = 0;
      } else {
        it--;
        j = *it;
      }

      // printf("right %d %dx%d\n", val, (t[val]-j) , (i2-i1));
      ans += val * (t[val]-j) * (i2-i1);
      END1: ;
    }

    {
      // 左側に最大値がある場合
      ll j2, j1, i;
      auto it = s.lower_bound(t[val]);
      if (it == s.begin()) {
        goto END2;
      }
      it--;
      j1 = *it;
      if (it == s.begin()) {
        j2 = 0;
      } else {
        it--;
        j2 = *it;
      }
      it = s.lower_bound(t[val]);
      if (it == s.end()) {
        i = N+1;
      } else {
        i = *it;
      }
      // printf("left %dx%d\n", val, (j1-j2), (i-t[val]));
      ans += val * (j1-j2) * (i-t[val]);

      END2: ;
    }

    s.insert(t[val]);
  } 
  cout << ans << endl;
  return 0;
}

提出情報

ジャッジ結果