oj.uz

Submission #489312

# Submission time Handle Problem Language Result Execution time Memory
489312 2021-11-22T08:51:58 Z SSRS Palindromes (APIO14_palindrome) C++14
100 / 100
 924 ms 102472 KB 
#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.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3488 KB Output is correct
2 Correct 17 ms 3860 KB Output is correct
3 Correct 17 ms 3552 KB Output is correct
4 Correct 17 ms 3744 KB Output is correct
5 Correct 18 ms 3424 KB Output is correct
6 Correct 19 ms 3488 KB Output is correct
7 Correct 17 ms 3556 KB Output is correct
8 Correct 18 ms 3400 KB Output is correct
9 Correct 18 ms 3448 KB Output is correct
10 Correct 18 ms 3300 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 30724 KB Output is correct
2 Correct 206 ms 30732 KB Output is correct
3 Correct 200 ms 30964 KB Output is correct
4 Correct 206 ms 40244 KB Output is correct
5 Correct 216 ms 28924 KB Output is correct
6 Correct 222 ms 30976 KB Output is correct
7 Correct 204 ms 31096 KB Output is correct
8 Correct 243 ms 29820 KB Output is correct
9 Correct 225 ms 30076 KB Output is correct
10 Correct 240 ms 29064 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 679 ms 98036 KB Output is correct
2 Correct 648 ms 99736 KB Output is correct
3 Correct 662 ms 98744 KB Output is correct
4 Correct 652 ms 102472 KB Output is correct
5 Correct 816 ms 95724 KB Output is correct
6 Correct 675 ms 99388 KB Output is correct
7 Correct 684 ms 99756 KB Output is correct
8 Correct 919 ms 95476 KB Output is correct
9 Correct 924 ms 95440 KB Output is correct
10 Correct 829 ms 93784 KB Output is correct
11 Correct 710 ms 97904 KB Output is correct
12 Correct 890 ms 95752 KB Output is correct