結果
問題 | 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;}