Submission #237091

#TimeUsernameProblemLanguageResultExecution timeMemory
237091nvmdava회문 (APIO14_palindrome)C++17
100 / 100
272 ms122496 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define ff first #define ss second mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define N 300005 const ll MOD = 1000000007; const int INF = 0x3f3f3f3f; ll mx = 1; struct Node{ Node *c[26], *p[19]; int sz = 0, de; int trav(){ for(int i = 0; i < 26; ++i){ if(!c[i]) continue; sz += c[i] -> trav(); delete(c[i]); c[i] = NULL; } mx = max(mx, 1LL * de * sz); return sz; } Node* go(int a){ if(c[a]) return c[a]; c[a] = new Node(); c[a] -> de = de + 2; c[a] -> p[0] = this; for(int i = 1; ; ++i){ c[a] -> p[i] = c[a] -> p[i - 1] -> p[i - 1]; if(!c[a] -> p[i]) break; } return c[a]; } } *r1 = new Node(); int d1[N]; Node *w1[N]; int a[N]; int lg[N]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); string s; cin>>s; for(int i = 2; i < N; i <<= 1) lg[i] = lg[i >> 1] + 1; r1 -> de = -1; int n = s.size(); for(int i = 0; i < n; ++i) a[i] = s[i] - 'a'; int lo = -1, r = -1; for(int i = 0; i < n; ++i){ if(r < i){ d1[i] = 1; w1[i] = r1 -> go(a[i]); } else { w1[i] = w1[lo - (i - lo)]; d1[i] = d1[lo - (i - lo)]; int w = max(0, d1[i] - (r - i)); d1[i] -= w; while(w){ w1[i] = w1[i] -> p[lg[w & -w]]; w -= w & -w; } } while(i + d1[i] < n && i - d1[i] >= 0 && a[i - d1[i]] == a[i + d1[i]]){ w1[i] = w1[i] -> go(a[i + d1[i]]); ++d1[i]; } ++w1[i] -> sz; if(r <= i + d1[i] - 1){ r = i + d1[i] - 1; lo = i; } } r1 -> trav(); r1 -> de = 0; lo = -1, r = -1; for(int i = 0; i < n; ++i){ if(r < i){ d1[i] = 0; w1[i] = r1; } else { w1[i] = w1[lo - (i - lo)]; d1[i] = d1[lo - (i - lo)]; int w = max(0, d1[i] - (r - i)); d1[i] -= w; while(w){ w1[i] = w1[i] -> p[lg[w & -w]]; w -= w & -w; } } while(i + d1[i] < n && i - d1[i] - 1 >= 0 && a[i - d1[i] - 1] == a[i + d1[i]]){ w1[i] = w1[i] -> go(a[i + d1[i]]); ++d1[i]; } ++w1[i] -> sz; if(r <= i + d1[i] - 1){ r = i + d1[i] - 1; lo = i; } } r1 -> trav(); cout<<mx; }
#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...