oj.uz

Submission #672840

# Submission time Handle Problem Language Result Execution time Memory
672840 2022-12-18T11:24:31 Z valerikk Palindromes (APIO14_palindrome) C++17
100 / 100
 417 ms 32612 KB 
#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(c[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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 0 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 472 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 472 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 392 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 468 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1368 KB Output is correct
2 Correct 7 ms 1372 KB Output is correct
3 Correct 8 ms 1368 KB Output is correct
4 Correct 10 ms 1368 KB Output is correct
5 Correct 8 ms 1288 KB Output is correct
6 Correct 8 ms 1368 KB Output is correct
7 Correct 7 ms 1372 KB Output is correct
8 Correct 7 ms 1240 KB Output is correct
9 Correct 7 ms 1232 KB Output is correct
10 Correct 8 ms 1368 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 10104 KB Output is correct
2 Correct 89 ms 10328 KB Output is correct
3 Correct 97 ms 11084 KB Output is correct
4 Correct 103 ms 10992 KB Output is correct
5 Correct 117 ms 10252 KB Output is correct
6 Correct 96 ms 10332 KB Output is correct
7 Correct 96 ms 10600 KB Output is correct
8 Correct 77 ms 9508 KB Output is correct
9 Correct 94 ms 9944 KB Output is correct
10 Correct 96 ms 10464 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 29920 KB Output is correct
2 Correct 305 ms 30200 KB Output is correct
3 Correct 325 ms 32548 KB Output is correct
4 Correct 330 ms 32612 KB Output is correct
5 Correct 417 ms 30260 KB Output is correct
6 Correct 359 ms 31028 KB Output is correct
7 Correct 384 ms 31340 KB Output is correct
8 Correct 380 ms 28200 KB Output is correct
9 Correct 352 ms 28156 KB Output is correct
10 Correct 404 ms 30984 KB Output is correct
11 Correct 289 ms 30296 KB Output is correct
12 Correct 354 ms 28440 KB Output is correct