Submission #489312

#	Time	Username	Problem	Language	Result	Execution time	Memory
489312		SSRS	Palindromes (APIO14_palindrome)	C++14	100 / 100	924 ms	102472 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000;
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){
  if (R - L == 1){
    return;
  }
  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(){
  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;
  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]);
  }
  for (int i = 0; i < N * 2 - 1; i++){
    ans2 = max(ans2, (long long) A[i]);
  }
  cout << ans2 << endl;
}

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