제출 #534030

#제출 시각아이디문제언어결과실행 시간메모리
534030getac회문 (APIO14_palindrome)C++14
0 / 100
817 ms36484 KiB
//InTheNameOfGOD //PRS;) #include<iostream> #include<algorithm> #include<vector> #define Fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define X first #define Y second using namespace std; typedef pair<int, int> pl; typedef pair<int, pl> pi; typedef long long ll; const int xn = 3e5 + 5; int r[xn << 1][20]; pi a[xn]; pl b[xn]; inline int lcp(int x, int y) { int t = 0; for(int i = 18; i >= 0; i--) if(r[x + t][i] == r[y + t][i]) t += (1 << i); return t; } int main() { Fast string s; cin >> s; int n = s.size(); for(int i = 0; i < n; i++) r[i][0] = s[i] - 'a' + 1; for(int j = 1; j < 20; j++) { int j1 = j - 1; for(int i = 0; i < n; i++) a[i] = {r[i][j1], {r[i + (1 << j1)][j1], i}}; sort(a, a + n); r[a[0].Y.Y][j] = 1; for(int i = 1; i < n; i++) { r[a[i].Y.Y][j] = r[a[i - 1].Y.Y][j]; if(a[i - 1].X < a[i].X || a[i - 1].Y.X < a[i].Y.X) r[a[i].Y.Y][j]++; } } for(int i = 0; i < n; i++) b[i] = {r[i][19], i}; sort(b, b + n); vector<pi> v; ll ans = n; for(int i = 1; i < n; i++) { int e = lcp(b[i - 1].Y, b[i].Y), prs = 0; while(!v.empty() && v.back().X >= e) { pi p = v.back(); v.pop_back(); if(p.X == e) continue; ans = max(ans, 1ll * (i - p.Y.X) * p.X); } if(!v.empty()) prs = v.back().Y.Y; v.push_back({e, {prs, i}}); } for(pi p : v) ans = max(ans, 1ll * (n - p.Y.X) * p.X); return cout << ans << '\n', 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...