結果
問題 | No.1996 <>< |
ユーザー |
![]() |
提出日時 | 2022-07-01 21:33:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 68 ms / 2,000 ms |
コード長 | 1,434 bytes |
コンパイル時間 | 2,052 ms |
コンパイル使用メモリ | 180,920 KB |
実行使用メモリ | 20,864 KB |
最終ジャッジ日時 | 2024-11-26 04:02:54 |
合計ジャッジ時間 | 3,273 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
#include <bits/stdc++.h> using namespace std; const long long MOD = 1000000007; template <typename T> struct binary_indexed_tree{ int N; vector<T> BIT; binary_indexed_tree(int N): N(N), BIT(N + 1, 0){ } void add(int i, T x){ i++; while (i <= N){ BIT[i] += x; i += i & -i; } } T sum(int i){ T ans = 0; while (i > 0){ ans += BIT[i]; i -= i & -i; } return ans; } T sum(int L, int R){ return sum(R) - sum(L); } }; int main(){ int N, K; cin >> N >> K; vector<int> A(N); for (int i = 0; i < N; i++){ cin >> A[i]; } vector<char> s(K); for (int i = 0; i < K; i++){ cin >> s[i]; } vector<int> B = A; sort(B.begin(), B.end()); B.erase(unique(B.begin(), B.end()), B.end()); for (int i = 0; i < N; i++){ A[i] = lower_bound(B.begin(), B.end(), A[i]) - B.begin(); } int cnt = B.size(); vector<vector<long long>> dp(K + 1, vector<long long>(N, 0)); for (int i = 0; i < N; i++){ dp[0][i] = 1; } for (int i = 0; i < K; i++){ binary_indexed_tree<long long> BIT(cnt); for (int j = 0; j < N; j++){ if (s[i] == '<'){ dp[i + 1][j] = BIT.sum(0, A[j]) % MOD; } if (s[i] == '>'){ dp[i + 1][j] = BIT.sum(A[j] + 1, cnt) % MOD; } BIT.add(A[j], dp[i][j]); } } long long ans = 0; for (int i = 0; i < N; i++){ ans += dp[K][i]; } ans %= MOD; cout << ans << endl; }