結果
問題 | No.465 PPPPPPPPPPPPPPPPAPPPPPPPP |
ユーザー |
![]() |
提出日時 | 2016-12-12 05:46:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 171 ms / 2,000 ms |
コード長 | 2,938 bytes |
コンパイル時間 | 2,007 ms |
コンパイル使用メモリ | 186,276 KB |
実行使用メモリ | 15,680 KB |
最終ジャッジ日時 | 2024-11-30 07:12:18 |
合計ジャッジ時間 | 4,428 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; struct Manacher { vector<int> rads; // O(|s|) Manacher(const string &s) : rads(s.size() * 2 - 1){ int size = (int) rads.size(); int i = 0, j = 0; while (i < size) { while (i - j >= 0 && i + j < size && get(s, i - j) == get(s, i + j)) { ++j; } rads[i] = j; int k = 1; while (i - k >= 0 && i + k < size && k + rads[i - k] < j) { rads[i + k] = rads[i - k], ++k; } i += k; j -= k; } } // s[l, r] is palindrome? // O(1) bool is_palindrome(int l, int r) { assert(l >= 0); assert(r >= l); assert(r * 2 <= (int) rads.size()); return rads[l + r] >= r - l + 1; } private: static char get(const string &s, int i) { if (i & 1) return '^'; else return s[i >> 1]; } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); string s; cin >> s; int n = s.size(); assert(n >= 4 && n <= 500000); for (char c : s) assert(c >= 'a' && c <= 'z'); Manacher mana(s); vector<int> pl(n); vector<int> gpl(n + 1); vector<tuple<int, int, int>> G; for (int j = 1; j <= n; j++) { // G -> G' vector<tuple<int, int, int>> H; for (const tuple<int, int, int> &idk : G) { int i, d, k; tie(i, d, k) = idk; if (i > 1 && s[i - 2] == s[j - 1]) { H.emplace_back(i - 1, d, k); } } // G' -> G'' deque<tuple<int, int, int>> I; int r = -j; for (const tuple<int, int, int> &idk : H) { int i, d, k; tie(i, d, k) = idk; if (i - r != d) { I.emplace_back(i, i - r, 1); if (k > 1) { I.emplace_back(i + d, d, k - 1); } } else { I.emplace_back(idk); } r = i + (k - 1) * d; } if (j > 1 && s[j - 2] == s[j - 1]) { I.emplace_back(j - 1, j - 1 - r, 1); r = j; } I.emplace_back(j, j - r, 1); G.clear(); // G'' -> next G int ip, dp, kp; tie(ip, dp, kp) = I.front(); I.pop_front(); for (const tuple<int, int, int> &idk : I) { int i, d, k; tie(i, d, k) = idk; if (dp == d) { kp += k; } else { G.emplace_back(ip, dp, kp); ip = i; dp = d; kp = k; } } G.emplace_back(ip, dp, kp); // calc pl for (const tuple<int, int, int> &idk : G) { int i, d, k; tie(i, d, k) = idk; r = i + (k - 1) * d; int m = 0; if (r - 2 >= 0) m += mana.is_palindrome(0, r - 2); if (k > 1 && i - d >= 0) { m += gpl[i - d]; } if (d <= i) { gpl[i - d] = m; } pl[j - 1] += m; } } vector<long long> sum_p2(n + 1); for (int i = 1; i < n; i++) sum_p2[i + 1] = sum_p2[i] + pl[i]; long long ans = 0; for (int k = 0; k < n - 1; k++) { if (mana.is_palindrome(k + 1, n - 1)) { ans += sum_p2[k]; } } cout << ans << endl; }