Submission #672839

#	Time	Username	Problem	Language	Result	Execution time	Memory
672839		valerikk	Palindromes (APIO14_palindrome)	C++17	0 / 100	254 ms	30288 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 3e5 + 7;

int n;
string s;
int d[N];
vector<pair<int, int>> kek;
int p[N], c[N], np[N], nc[N];
int lcp[N];

int md(int i) {
  if (i < 0) {
    return i + n;
  }
  if (i >= n) {
    return i - n;
  }
  return i;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> s;
  n = s.size();
  for (int i = 0, l = 0, r = -1; i < n; ++i) {
    if (i < r) {
      d[i] = min(r - i, d[l + r - i]);
    }
    kek.push_back({1, i});
    while (i - d[i] - 1 >= 0 && i + d[i] + 1 < n &&
           s[i - d[i] - 1] == s[i + d[i] + 1]) {
      ++d[i];
      kek.push_back({2 * d[i] + 1, i - d[i]});
    }
    if (i + d[i] > r) {
      l = i - d[i];
      r = i + d[i];
    }
  }
  memset(d, 0, n * sizeof d[0]);
  for (int i = 0, l = 0, r = -1; i < n - 1; ++i) {
    if (i < r) {
      d[i] = min(r - i, d[l + r - i - 1]);
    }
    while (i - d[i] >= 0 && i + d[i] + 1 < n &&
           s[i - d[i]] == s[i + d[i] + 1]) {
      ++d[i];
      kek.push_back({2 * d[i], i - d[i] + 1});
    }
    if (i + d[i] > r) {
      l = i - d[i] + 1;
      r = i + d[i];
    }
  }
  s.push_back('#');
  ++n;
  for (int i = 0; i < n; ++i) {
    p[i] = i;
  }
  sort(p, p + n, [&](int i, int j) { return s[i] < s[j]; });
  c[p[0]] = 0;
  for (int i = 1; i < n; ++i) {
    c[p[i]] = c[p[i - 1]] + (s[p[i]] != s[p[i - 1]]);
  }
  for (int k = 1; k < n; k <<= 1) {
    static int st[N];
    memset(st, 0, n * sizeof st[0]);
    for (int i = 0; i < n; ++i) {
      ++st[c[i]];
    }
    for (int i = 1; i < n; ++i) {
      st[i] += st[i - 1];
    }
    for (int i = n - 1; i >= 0; --i) {
      int j = md(p[i] - k);
      np[--st[c[j]]] = j;
    }
    memcpy(p, np, n * sizeof p[0]);
    nc[p[0]] = 0;
    for (int i = 1; i < n; ++i) {
      nc[p[i]] = nc[p[i - 1]] + (c[p[i]] != c[p[i - 1]] ||
                                 c[md(p[i] + k)] != c[md(p[i - 1] + k)]);
    }
    memcpy(c, nc, n * sizeof c[0]);
  }
  for (int i = 1; i < n; ++i) {
    p[i - 1] = p[i];
  }
  --n;
  for (int i = 0; i < n; ++i) {
    --c[i];
  }
  for (int i = 0, j = 0; i < n; ++i, j = max(0, j - 1)) {
    if (c[i] == n - 1) {
      continue;
    }
    int nx = p[c[i] + 1];
    while (max(i, nx) + j < n && s[i + j] == s[nx + j]) {
      ++j;
    }
    lcp[c[i]] = j;
  }
  sort(kek.begin(), kek.end());
  vector<pair<int, int>> lol;
  for (int i = 0; i < n - 1; ++i) {
    lol.push_back({lcp[i], i});
  }
  sort(lol.begin(), lol.end());
  int ptr = 0;
  set<int> st;
  ll ans = 0;
  for (auto [len, i] : kek) {
    while (ptr < (int)lol.size() && lol[ptr].first < len) {
      st.insert(lol[ptr].second);
      ++ptr;
    }
    int l = 0, r = n - 1;
    auto it = st.lower_bound(i);
    if (it != st.end()) {
      r = *it;
    }
    if (it != st.begin()) {
      l = *prev(it) + 1;
    }
    ans = max(ans, 1ll * len * (r - l + 1));
  }
  cout << ans << endl;
  return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27