提出 #28442072

---

ソースコード 拡げる

/*
 * Author: nskybytskyi
 * Time:   2022-01-08 14:00:00
 */

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

using mint = modint998244353;

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int n;
  cin >> n;

  vector<int> a(n);
  for (auto& ai : a) {
    cin >> ai;
  }

  vector<mint> dp(n + 1);
  dp[0] = 1;

  stack<pair<int, mint>> mn, mx;
  mint mx_sum = 0, mn_sum = 0;

  for (int i = 0; i < n; ++i) {
    {  // max
      mint sum = 0;
      while (!mx.empty() && a[mx.top().first] <= a[i]) {
        auto [j, dp_sum] = mx.top();
        mx.pop();
        mx_sum -= a[j] * dp_sum;
        sum += dp_sum;
      }
      mx_sum += sum * a[i];
      mx.emplace(i, sum + dp[i]);
    }

    {  // min
      mint sum = 0;
      while (!mn.empty() && a[mn.top().first] >= a[i]) {
        auto [j, dp_sum] = mn.top();
        mn.pop();
        mn_sum -= a[j] * dp_sum;
        sum += dp_sum;
      }
      mn_sum += sum * a[i];
      mn.emplace(i, sum + dp[i]);
    }

    dp[i + 1] = mx_sum - mn_sum;
  }

  cout << dp[n].val() << "\n";

  return 0;
}

提出情報

ジャッジ結果