提出 #44017066

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; ++i) cin >> A[i];

  // index
  vector<int> stack;
  vector<pair<int, int>> LR;

  for (int i = N - 1; i >= 0; --i) {
    stack.emplace_back(i);
    int nxt = 1;
    while (!stack.empty() && A[stack.back()] == nxt) {
      int L = i, R = stack.back();
      // L is the largest index, s.t, (A_L, ..., A_R) is generatable.
      LR.emplace_back(L, R);
      stack.pop_back();
      ++nxt;
    }
  }

  reverse(LR.begin(), LR.end());
  vector<int> dp(N);
  for (auto [L, R]: LR) { dp[R] = (L == 0 ? 1 : dp[L - 1] + 1); }

  ll ANS = 0;
  for (int x: dp) ANS += x;
  cout << ANS << '\n';
}

int main() {
  solve();
  return 0;
}

提出情報

ジャッジ結果