Submission #388114

#TimeUsernameProblemLanguageResultExecution timeMemory
388114KeshiPalindromes (APIO14_palindrome)C++17
73 / 100
1094 ms57908 KiB
//In the name of God #include <bits/stdc++.h> #pragma GCC optimize("O2") using namespace std; typedef int ll; typedef pair<ll, ll> pll; const ll maxn = 3e5 + 100; const ll lg = 19; const ll mod = 1e9 + 7; const ll inf = 1e9; #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout); #define pb push_back #define Mp make_pair #define F first #define S second #define Sz(x) ll((x).size()) #define all(x) (x).begin(), (x).end() #define lc (id << 1) #define rc (lc | 1) ll n, p[maxn], rnk[maxn], r2[maxn], lcp[maxn], f[maxn], per[maxn], ps[maxn], p2[maxn]; string s; vector<ll> vec[maxn]; ll mn[lg][maxn]; void bld(){ for(ll i = 0; i < n; i++){ mn[0][i] = lcp[i]; } for(ll i = 1; i < lg; i++){ for(ll j = 0; j + (1 << i) <= n; j++){ mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << (i - 1))]); } } } ll get(ll l, ll r){ if(l == r) return inf; ll t = r - l; ll i = f[t]; return min(mn[i][l], mn[i][r - (1 << i)]); } int main(){ fast_io; for(ll i = 2; i < maxn; i++){ f[i] = f[i / 2] + 1; } cin >> s; s += '#'; n = Sz(s); ll cnt = 300; for(ll i = 0; i < n; i++){ ps[(ll)s[i]]++; } for(ll i = 1; i < cnt; i++){ ps[i] += ps[i - 1]; } for(ll i = n; i--;){ per[--ps[(ll)s[i]]] = i; } rnk[per[0]] = 0; cnt = 1; for(ll i = 1; i < n; i++){ if(s[per[i - 1]] != s[per[i]]) cnt++; rnk[per[i]] = cnt - 1; } for(ll h = 0; (1 << h) < n; h++){ fill(ps, ps + cnt, 0); for(ll i = 0; i < n; i++){ p2[i] = per[i] - (1 << h); if(p2[i] < 0) p2[i] += n; } for(ll i = 0; i < n; i++){ ps[rnk[p2[i]]]++; } for(ll i = 1; i < cnt; i++){ ps[i] += ps[i - 1]; } for(ll i = n; i--;){ per[--ps[rnk[p2[i]]]] = p2[i]; } for(ll i = 0; i < n; i++){ p2[i] = per[i] + (1 << h); if(p2[i] >= n) p2[i] -= n; } r2[per[0]] = 0; cnt = 1; for(ll i = 1; i < n; i++){ if(rnk[per[i]] != rnk[per[i - 1]] || rnk[p2[i]] != rnk[p2[i - 1]]) cnt++; r2[per[i]] = cnt - 1; } for(ll i = 0; i < n; i++){ rnk[i] = r2[i]; } } for(ll i = 0; i < n; i++){ p[i] = per[i]; } for(ll i = 0, k = 0; i < n; i++){ if(rnk[i] == n - 1){ k = 0; continue; } ll j = p[rnk[i] + 1]; while(i + k < n && j + k < n && s[i + k] == s[j + k]) k++; lcp[rnk[i]] = k; if(k) k--; } bld(); n--; vector<int> d1(n); for (int i = 0, l = 0, r = -1; i < n; i++) { int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1); while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) { k++; } d1[i] = k--; if (i + k > r) { l = i - k; r = i + k; } } vector<int> d2(n); for (int i = 0, l = 0, r = -1; i < n; i++) { int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1); while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) { k++; } d2[i] = k--; if (i + k > r) { l = i - k - 1; r = i + k; } } set<ll> st; long long ans = 0; for(ll i = n; i--;){ for(ll j : vec[i]){ st.erase(j); } vec[i].clear(); st.insert(i); vec[i - d1[i]].pb(i); auto it = st.rbegin(); while(it != st.rend()){ ll t = (*it - i) * 2 + 1; if(t <= lcp[rnk[i] - 1]) break;; ll l = rnk[i], r = n + 1; while(r - l > 1){ ll mid = (l + r) >> 1; if(get(rnk[i], mid) >= t) l = mid; else r = mid; } ans = max(ans, ((long long)t) * (r - rnk[i])); it++; } } st.clear(); for(ll i = n - 1; i--;){ for(ll j : vec[i]){ st.erase(j); } if(d2[i + 1]) st.insert(i); if(d2[i + 1]) vec[i - d2[i + 1]].pb(i); if(st.empty()) continue; auto it = st.rbegin(); while(it != st.rend()){ ll t = (*it - i) * 2 + 2; if(t <= lcp[rnk[i] - 1]) break; ll l = rnk[i], r = n + 1; while(r - l > 1){ ll mid = (l + r) >> 1; if(get(rnk[i], mid) >= t) l = mid; else r = mid; } ans = max(ans, ((long long)t) * (r - rnk[i])); it++; } } cout << ans; return 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...