結果
問題 |
No.992 最長増加部分列の数え上げ
|
ユーザー |
|
提出日時 | 2025-05-03 17:26:40 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 250 ms / 2,000 ms |
コード長 | 1,357 bytes |
コンパイル時間 | 4,126 ms |
コンパイル使用メモリ | 292,416 KB |
実行使用メモリ | 26,012 KB |
最終ジャッジ日時 | 2025-05-03 17:26:54 |
合計ジャッジ時間 | 13,338 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/modint> #include <atcoder/segtree> using namespace std; using mint = atcoder::modint1000000007; using ll = long long; using S = pair<ll, mint>; S op(S a, S b) { if(a.first == b.first) return S{a.first, a.second + b.second}; if(a.first < b.first) swap(a, b); return S{a.first, a.second}; } S e() { return S{-1, 0}; } int opmax(int a, int b) { return max(a, b); } int emax() { return 0; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); int N; cin >> N; vector<int> A(N); for(int i = 0; i < N; i++) cin >> A[i]; vector<int> cc = A; sort(cc.begin(), cc.end()); cc.erase(unique(cc.begin(), cc.end()), cc.end()); for(int i = 0; i < N; i++) A[i] = (lower_bound(cc.begin(), cc.end(), A[i]) - cc.begin()) + 1; atcoder::segtree<S, op, e> ep(N + 2); atcoder::segtree<int, opmax, emax> dp(N + 1); vector<vector<int>> B(N + 1); for(int i = 0; i < N; i++) B[A[i]].push_back(i); ep.set(0, {0, 1}); for(int it = 1; it <= N; it++) if(!B[it].empty()) { const int sz = B[it].size(); for(int j = sz - 1; j >= 0; j--) { int i = B[it][j] + 1; dp.set(i, dp.prod(0, i) + 1); ep.set(i, {dp.get(i), ep.prod(0, i).second}); } } int MAX = dp.all_prod(); mint ans = 0; for(int i = 1; i <= N; i++) if(dp.get(i) == MAX) ans += ep.get(i).second; cout << ans.val() << "\n"; }