結果
問題 | No.1848 Long Prefixes |
ユーザー |
![]() |
提出日時 | 2021-12-23 13:10:36 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 86 ms / 2,000 ms |
コード長 | 1,528 bytes |
コンパイル時間 | 4,475 ms |
コンパイル使用メモリ | 277,752 KB |
実行使用メモリ | 7,168 KB |
最終ジャッジ日時 | 2024-06-29 07:58:52 |
合計ジャッジ時間 | 6,733 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
#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 = atcoder::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;}