Submission #489307

#TimeUsernameProblemLanguageResultExecution timeMemory
489307SSRSPalindromes (APIO14_palindrome)C++14
73 / 100
1087 ms115296 KiB
#pragma GCC target("avx2") #pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; const int INF = 10000000; vector<int> suffix_array(string S){ S.push_back(0); int N = S.size(); vector<int> cnt(128, 0); for (int i = 0; i < N; i++){ cnt[S[i]]++; } for (int i = 0; i < 127; i++){ cnt[i + 1] += cnt[i]; } vector<int> SA(N); for (int i = 0; i < N; i++){ cnt[S[i]]--; SA[cnt[S[i]]] = i; } vector<int> rank(N); rank[SA[0]] = 0; for (int i = 0; i < N - 1; i++){ rank[SA[i + 1]] = rank[SA[i]]; if (S[SA[i]] != S[SA[i + 1]]){ rank[SA[i + 1]]++; } } int L = 1; while (L < N){ vector<int> SA2(N); for (int i = 0; i < N; i++){ SA2[i] = SA[i] - L; if (SA2[i] < 0){ SA2[i] += N; } } cnt = vector<int>(N, 0); for (int i = 0; i < N; i++){ cnt[rank[SA2[i]]]++; } for (int i = 0; i < N - 1; i++){ cnt[i + 1] += cnt[i]; } for (int i = N - 1; i >= 0; i--){ cnt[rank[SA2[i]]]--; SA[cnt[rank[SA2[i]]]] = SA2[i]; } vector<int> rank2(N); rank2[SA[0]] = 0; for (int i = 0; i < N - 1; i++){ rank2[SA[i + 1]] = rank2[SA[i]]; if (rank[SA[i]] != rank[SA[i + 1]] || rank[(SA[i] + L) % N] != rank[(SA[i + 1] + L) % N]){ rank2[SA[i + 1]]++; } } rank = rank2; L *= 2; } SA.erase(SA.begin()); return SA; } vector<int> lcp_array(string &S, vector<int> &SA){ int N = S.size(); vector<int> rank(N); for (int i = 0; i < N; i++){ rank[SA[i]] = i; } vector<int> lcp(N - 1, 0); int h = 0; for (int i = 0; i < N; i++){ if (rank[i] > 0){ int prev = SA[rank[i] - 1]; if (h > 0){ h--; } while (i + h < N && prev + h < N){ if (S[i + h] != S[prev + h]){ break; } h++; } lcp[rank[i] - 1] = h; } } return lcp; } struct segment_tree_min{ int N; vector<pair<int, int>> ST; segment_tree_min(vector<int> &A){ int N2 = A.size(); N = 1; while (N < N2){ N *= 2; } ST = vector<pair<int, int>>(N * 2 - 1, make_pair(INF, INF)); for (int i = 0; i < N2; i++){ ST[N - 1 + i] = make_pair(A[i], i); } for (int i = N - 2; i >= 0; i--){ ST[i] = min(ST[i * 2 + 1], ST[i * 2 + 2]); } } pair<int, int> range_min(int L, int R, int i, int l, int r){ if (r <= L || R <= l){ return make_pair(INF, INF); } else if (L <= l && r <= R){ return ST[i]; } else { int m = (l + r) / 2; return min(range_min(L, R, i * 2 + 1, l, m), range_min(L, R, i * 2 + 2, m, r)); } } pair<int, int> range_min(int L, int R){ return range_min(L, R, 0, 0, N); } }; void dfs(vector<tuple<int, int, int>> &query, vector<int> &SA, segment_tree_min &LCP, int L, int R){ int N = SA.size(); if (R - L == 1){ query.push_back(make_tuple(SA[L], N, 1)); } else { pair<int, int> P = LCP.range_min(L, R - 1); int mn = P.first; int m = P.second + 1; if (mn > 0){ query.push_back(make_tuple(SA[L], SA[L] + mn, R - L)); } dfs(query, SA, LCP, L, m); dfs(query, SA, LCP, m, R); } } vector<int> manacher(string S){ int N = S.size(); vector<int> ans(N, 0); int i = 0, j = 0; while (i < N){ while (i >= j && i + j < N && S[i - j] == S[i + j]){ j++; } ans[i] = j; int k = 1; while (i >= k && i + k < N && k + ans[i - k] < j){ ans[i + k] = ans[i - k]; k++; } i += k; j -= k; } return ans; } struct segment_tree_max{ int N; vector<int> ST; segment_tree_max(int N2){ N = 1; while (N < N2){ N *= 2; } ST = vector<int>(N * 2 - 1, -INF); } segment_tree_max(vector<int> A){ int N2 = A.size(); N = 1; while (N < N2){ N *= 2; } ST = vector<int>(N * 2 - 1, -INF); for (int i = 0; i < N2; i++){ ST[N - 1 + i] = A[i]; } for (int i = N - 2; i >= 0; i--){ ST[i] = max(ST[i * 2 + 1], ST[i * 2 + 2]); } } void update(int i, int x){ i += N - 1; ST[i] = x; while (i > 0){ i = (i - 1) / 2; ST[i] = max(ST[i * 2 + 1], ST[i * 2 + 2]); } } int range_max(int L, int R, int i, int l, int r){ if (r <= L || R <= l){ return -INF; } else if (L <= l && r <= R){ return ST[i]; } else { int m = (l + r) / 2; return max(range_max(L, R, i * 2 + 1, l, m), range_max(L, R, i * 2 + 2, m, r)); } } int range_max(int L, int R){ return range_max(L, R, 0, 0, N); } }; int main(){ ios::sync_with_stdio(false); string S; cin >> S; int N = S.size(); vector<int> SA = suffix_array(S); vector<int> LCP = lcp_array(S, SA); segment_tree_min ST(LCP); vector<tuple<int, int, int>> query; query.reserve(N * 2); dfs(query, SA, ST, 0, N); int Q = query.size(); vector<int> L(Q), R(Q), X(Q); for (int i = 0; i < Q; i++){ L[i] = get<0>(query[i]); R[i] = get<1>(query[i]); X[i] = get<2>(query[i]); } string T = "$"; for (int i = 0; i < N; i++){ T += S[i]; T += '$'; } vector<int> A = manacher(T); A.erase(A.begin()); A.pop_back(); for (int i = 0; i < N * 2 - 1; i++){ A[i]--; } vector<int> l(N * 2 - 1), r(N * 2 - 1); for (int i = 0; i < N * 2 - 1; i++){ l[i] = i / 2 - (A[i] - 1) / 2; r[i] = i / 2 + (A[i] + 2) / 2; } vector<int> B(N * 2 - 1), C(N * 2 - 1); for (int i = 0; i < N * 2 - 1; i++){ B[i] = A[i] + l[i] * 2; C[i] = A[i] - r[i] * 2; } vector<int> ans(Q, 0); { vector<vector<int>> upd1(N * 2), query1(N * 2); for (int i = 0; i < N * 2 - 1; i++){ upd1[l[i]].push_back(i); } for (int i = 0; i < Q; i++){ query1[L[i]].push_back(i); } segment_tree_max ST1(N * 2 - 1); segment_tree_max ST2(A); for (int i = 0; i < N * 2; i++){ for (int j : upd1[i]){ ST1.update(j, B[j]); ST2.update(j, -INF); } for (int j : query1[i]){ ans[j] = max(ans[j], ST1.range_max(L[j] * 2, L[j] + R[j]) - L[j] * 2); ans[j] = max(ans[j], ST2.range_max(L[j] * 2, L[j] + R[j])); } } } { vector<vector<int>> upd2(N * 2), query2(N * 2); for (int i = 0; i < N * 2 - 1; i++){ upd2[r[i]].push_back(i); } for (int i = 0; i < Q; i++){ query2[R[i]].push_back(i); } segment_tree_max ST3(C); segment_tree_max ST4(N * 2 - 1); for (int i = 0; i < N * 2; i++){ for (int j : upd2[i]){ ST3.update(j, -INF); ST4.update(j, A[j]); } for (int j : query2[i]){ ans[j] = max(ans[j], ST3.range_max(L[j] + R[j], R[j] * 2 - 1) + R[j] * 2); ans[j] = max(ans[j], ST4.range_max(L[j] + R[j], R[j] * 2 - 1)); } } } long long ans2 = 0; for (int i = 0; i < Q; i++){ ans2 = max(ans2, (long long) ans[i] * X[i]); } cout << ans2 << endl; }
#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...