結果
問題 | No.1996 <>< |
ユーザー |
![]() |
提出日時 | 2022-07-01 22:38:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 87 ms / 2,000 ms |
コード長 | 1,076 bytes |
コンパイル時間 | 6,883 ms |
コンパイル使用メモリ | 262,360 KB |
最終ジャッジ日時 | 2025-01-30 03:12:33 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/all>using namespace std;#define rep(i, n) for (int i = 0; i < (int)(n); i++)using namespace atcoder;typedef long long ll;const ll INF = 1e18;typedef modint1000000007 mint;//cout << fixed << setprecision(12);int main(){int n, k;cin >> n >> k;vector<int> a(n);rep(i,n){cin >> a[i];}vector<int> b = a;sort(b.begin(), b.end());b.erase(unique(b.begin(), b.end()), b.end());unordered_map<int,int> a_c;for(int i=0; i<b.size(); i++){a_c[b[i]] = i;}vector<int> a_z(n);rep(i,n){a_z[i] = a_c[a[i]];}int azs = a_z.size();vector<char> s(k);rep(i,k){cin >> s[i];}vector<vector<mint>> dp(k+1,vector<mint>(n));rep(i,n){dp[0][i] = 1;}rep(num,k){fenwick_tree<mint> bit(azs);if(s[num] == '<'){rep(i,n){dp[num+1][i] += bit.sum(0, a_z[i]);bit.add(a_z[i], dp[num][i]);}}else{rep(i,n){dp[num+1][i] += bit.sum(a_z[i]+1, azs);bit.add(a_z[i], dp[num][i]);}}}mint ans = 0;rep(i,n){ans += dp[k][i];}cout << ans.val() << endl;}