結果
問題 | No.1848 Long Prefixes |
ユーザー |
![]() |
提出日時 | 2021-12-23 13:12:39 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,519 bytes |
コンパイル時間 | 4,933 ms |
コンパイル使用メモリ | 282,680 KB |
実行使用メモリ | 19,328 KB |
最終ジャッジ日時 | 2024-06-29 07:59:04 |
合計ジャッジ時間 | 11,430 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | TLE * 1 -- * 39 |
ソースコード
#pragma GCC target("avx2")#include <bits/stdc++.h>#include <atcoder/string>#include <atcoder/modint>using namespace std;using Modint = atcoder::modint1000000007;template<class T> vector<int> z_algorithm(vector<T> A){const int N = A.size();vector<int> a(N);{auto B = A;sort(B.begin(), B.end());for(int i = 0; i < N; i++) a[i] = lower_bound(B.begin(), B.end(), A[i]) - B.begin();}vector<int> ans(N);for(int i = 0; i < N; i++){const int c = a[i];for(int j = i; j < N; j++){if(a[j] == c && ans[j - i] == i) ans[j - i]++;}}return ans;}int main(){int N;cin >> N;vector<pair<char, int>> A(N);for(auto& [c, a] : A) cin >> a;for(auto& [c, a] : A) cin >> c;auto Z = z_algorithm(vector(A.begin() + 1, A.end()));Z.push_back(0);vector<Modint> sum(N);sum[0] = Modint::raw(A[0].second);for(int i = 1; i < N; i++) sum[i] = sum[i - 1] + Modint::raw(A[i].second);const auto [c0, a0] = A[0];Modint ans = 0;for(int i = 0; i < N; i++) if(auto [c, a] = A[i]; c == c0){if(a < a0){ans += uint64_t(a) * (a + 1) / 2;continue;}ans += uint64_t(a0) * (a + a - a0 - 1) / 2;const int z = Z[i];ans += sum[z];if(i + 1 + z < N && A[i + 1 + z].first == A[1 + z].first){ans += Modint::raw(min(A[i + 1 + z].second, A[1 + z].second));}}cout << ans.val() << endl;}