結果
問題 | No.2433 Min Increasing Sequence |
ユーザー |
![]() |
提出日時 | 2023-08-18 21:49:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 41 ms / 2,000 ms |
コード長 | 1,873 bytes |
コンパイル時間 | 1,790 ms |
コンパイル使用メモリ | 204,020 KB |
最終ジャッジ日時 | 2025-02-16 09:53:47 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
#include <bits/stdc++.h> #ifdef LOCAL #include <debug.hpp> #else #define debug(...) void(0) #endif #include "atcoder/modint" #include "atcoder/segtree" using namespace std; typedef long long ll; #define all(x) begin(x), end(x) constexpr int INF = (1 << 30) - 1; constexpr long long IINF = (1LL << 60) - 1; constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; template <class T> istream& operator>>(istream& is, vector<T>& v) { for (auto& x : v) is >> x; return is; } template <class T> ostream& operator<<(ostream& os, const vector<T>& v) { auto sep = ""; for (const auto& x : v) os << exchange(sep, " ") << x; return os; } template <class T, class U = T> bool chmin(T& x, U&& y) { return y < x and (x = forward<U>(y), true); } template <class T, class U = T> bool chmax(T& x, U&& y) { return x < y and (x = forward<U>(y), true); } template <class T> void mkuni(vector<T>& v) { sort(begin(v), end(v)); v.erase(unique(begin(v), end(v)), end(v)); } template <class T> int lwb(const vector<T>& v, const T& x) { return lower_bound(begin(v), end(v), x) - begin(v); } using mint = atcoder::modint998244353; struct S { int val, idx; S(int val, int idx) : val(val), idx(idx) {} }; S op(S l, S r) { return r.val < l.val ? r : l; } S e() { return S(INF, -1); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector<int> A(N); cin >> A; vector<mint> dp(N + 1, 0); dp[0] = 1; dp[1] = -1; vector<S> init; for (int i = 0; i < N; i++) init.emplace_back(A[i], i); atcoder::segtree<S, op, e> seg(init); for (int i = 0; i <= N; i++) { if (i - 1 >= 0) dp[i] += dp[i - 1]; if (i == N) break; int need = seg.prod(i, N).idx; dp[need + 1] += dp[i]; } mint ans = dp[N]; cout << ans.val() << '\n'; return 0; }