結果
問題 |
No.1996 <><
|
ユーザー |
![]() |
提出日時 | 2024-12-01 17:13:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 83 ms / 2,000 ms |
コード長 | 1,193 bytes |
コンパイル時間 | 2,527 ms |
コンパイル使用メモリ | 211,332 KB |
最終ジャッジ日時 | 2025-02-26 10:07:57 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/fenwicktree> #include <atcoder/modint> using namespace std; using namespace atcoder; using mint = modint1000000007; void compress_vec(vector<int>& a){ vector<int> b = a; sort(b.begin(), b.end()); b.erase(unique(b.begin(), b.end()), b.end()); unordered_map<int, int> mp = {}; for(int i = 0; i < (int)b.size(); ++i){ mp[b[i]] = i; } for(int i = 0; i < (int)a.size(); ++i){ a[i] = mp[a[i]]; } } int main(){ int N, K; cin >> N >> K; vector<int> a(N); for(auto& x : a){ cin >> x; } compress_vec(a); string s; cin >> s; vector<vector<mint> > dp(K + 1, vector<mint>(N)); for(auto& x : dp[0]){ x = 1; } for(int i = 0; i < K; ++i){ fenwick_tree<mint> bt(N); for(int j = 0; j < N; ++j){ bt.add(a[j], dp[i][j]); if(s[i] == '<'){ dp[i + 1][j] = bt.sum(0, a[j]); } else{ dp[i + 1][j] = bt.sum(a[j] + 1, N); } } } mint ans = 0; for(auto& x : dp[K]){ ans += x; } cout << ans.val() << endl; return 0; }