Submission #88927

#TimeUsernameProblemLanguageResultExecution timeMemory
88927AnaiPalindromes (APIO14_palindrome)C++11
15 / 100
1064 ms3348 KiB
#include <bits/stdc++.h> #define x first #define y second using namespace std; using i64 = long long; using pii = pair<int, int>; const int N = 6e5 + 5, LG = 20; int pal[N], sa[LG][N]; char str[N]; vector<int> sorted; int n; static void add_stars() { char tmp[N]; n = 0; for (int i = 1; str[i]; ++i) { tmp[2 * i - 1] = '*'; tmp[2 * i] = str[i]; n+= 2; } tmp[n + 1] = '*'; tmp[n + 2] = 0; strcpy(str + 1, tmp + 1); } static void manacher() { int mid, r; str[n + 1] = '$'; str[0] = '#'; r = -1; for (int i = 1; i <= n; ++i) { pal[i] = 1; if (i > r) { while (str[i - pal[i]] == str[i + pal[i]]) pal[i]+= 1; mid = i; r = mid + pal[i] - 1; } else { pal[i] = min(r - i + 1, pal[mid - (i - mid)]); while (str[i - pal[i]] == str[i + pal[i]]) pal[i]+= 1; } } } static void build_sa() { pii lst; int ptr; sorted.resize(n); iota(begin(sorted), end(sorted), 1); for (int i = 1; i <= n; ++i) sa[0][i] = str[i]; for (int lg = 1; lg < LG; ++lg) { function<pii(int)> sa_pair = [&](int p) { return pii(sa[lg - 1][p], p + (1 << lg - 1) <= n ? sa[lg - 1][p + (1 << lg - 1)] : 0); }; sort(begin(sorted), end(sorted), [&](const int &a, const int &b) { return sa_pair(a) < sa_pair(b); }); lst = {-1, -1}; ptr = 0; for (auto i: sorted) { if (sa_pair(i) != lst) ++ptr; sa[lg][i] = ptr; lst = sa_pair(i); } } } static int lcp(int a, int b) { if (str[a] != str[b]) return 0; int len = 0, ant = min(pal[a], pal[b]); bool flag = ('a' <= str[a] && str[a] <= 'z'); for (int lg = LG - 1; lg >= 0; --lg) if (sa[lg][a] == sa[lg][b]) { a+= 1 << lg; b+= 1 << lg; len+= 1 << lg; } return 2 * min(len / 2, ant / 2) - int(flag); } static i64 skyline() { vector<int> stk, st, dr, val; int tsiz = sorted.size(); i64 ant = 0; for (auto i: sorted) ant = max(ant, pal[i] - 1LL); tsiz = sorted.size(); for (auto &v: {&st, &dr, &val, &stk}) v->reserve(tsiz); for (int i = 1; i < tsiz; ++i) val.push_back(lcp(sorted[i - 1], sorted[i])); for (int i = 0; i < val.size(); ++i) { while (!stk.empty() && val[stk.back()] >= val[i]) stk.pop_back(); st.push_back(stk.empty() ? 0 : stk.back() + 1); stk.push_back(i); } stk.clear(); for (int i = val.size() - 1; i >= 0; --i) { while (!stk.empty() && val[stk.back()] >= val[i]) stk.pop_back(); dr.push_back(stk.empty() ? tsiz - 2 : stk.back() - 1); stk.push_back(i); } reverse(begin(dr), end(dr)); for (int i = 0; i < tsiz - 1; ++i) ant = max(ant, i64(dr[i] - st[i] + 2) * val[i]); return ant; } int main() { #ifdef HOME freopen("apio_palindromes.in", "r", stdin); freopen("apio_palindromes.out", "w", stdout); #endif ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> (str + 1); add_stars(); n = strlen(str + 1); manacher(); build_sa(); cout << skyline() << endl; return 0; }

Compilation message (stderr)

palindrome.cpp: In lambda function:
palindrome.cpp:58:43: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
    return pii(sa[lg - 1][p], p + (1 << lg - 1) <= n ? sa[lg - 1][p + (1 << lg - 1)] : 0); };
                                        ~~~^~~
palindrome.cpp:58:79: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
    return pii(sa[lg - 1][p], p + (1 << lg - 1) <= n ? sa[lg - 1][p + (1 << lg - 1)] : 0); };
                                                                            ~~~^~~
palindrome.cpp: In function 'i64 skyline()':
palindrome.cpp:99:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < val.size(); ++i) {
                  ~~^~~~~~~~~~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:43:36: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
    pal[i] = min(r - i + 1, pal[mid - (i - mid)]);
                                ~~~~^~~~~~~~~~~
palindrome.cpp:29:6: note: 'mid' was declared here
  int mid, r;
      ^~~
#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...