oj.uz

Submission #1106228

# Submission time Handle Problem Language Result Execution time Memory
1106228 2024-10-29T15:18:52 Z ducanh1234 Palindromes (APIO14_palindrome) C++17
100 / 100
 680 ms 36268 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 300'000 + 10;
string s;
int n;
 
struct Hash { 
  int base, M;
  vector<int> h, rh, pw;
  Hash() : base(0), M(0) {}
  Hash(string s, int base, int M) : base(base), M(M), h(s.size() + 1), rh(s.size() + 1), pw(s.size() + 1) { 
    pw[0] = 1;
    for (int i = 1; i <= n; ++i) { 
      pw[i] = 1ll * pw[i - 1] * base % M;
      h[i] = (1ll * h[i - 1] * base % M + s[i - 1]) % M;
      rh[i] = (1ll * rh[i - 1] * base % M + s[n - i]) % M;
    }
  }
 
  int get(int l, int r) { 
    return (h[r] - 1ll * h[l - 1] * pw[r - l + 1] % M + M) % M; 
  }
  int rget(int l, int r) { 
    return (rh[r] - 1ll * rh[l - 1] * pw[r - l + 1] % M + M) % M; 
  }
} T[2];
 
using HASH = pair<int, int>;
inline HASH get(int l, int r) { 
  return make_pair(T[0].get(l, r), T[1].get(l, r));
}
inline HASH rget(int l, int r) { 
  tie(l, r) = make_pair(n - r + 1, n - l + 1);
  return make_pair(T[0].rget(l, r), T[1].rget(l, r));
}
inline bool chk(int l, int r) { return get(l, r) == rget(l, r); }
 
int pos[N], tmp[N], sa[N];
int lcp[N];
 
void initSA() { 
  for (int i = 1; i <= n; ++i) pos[i] = s[i] - 'a' + 1, sa[i] = i;
  for (int gap = 1; ; gap *= 2) { 
    auto cmp = [&](int i, int j) { 
      if (pos[i] != pos[j]) return pos[i] < pos[j];
      i += gap; j += gap;
      return i <= n && j <= n ? pos[i] < pos[j] : i > j;
    };
    
    sort(sa + 1, sa + n + 1, cmp);
    for (int i = 2; i <= n; ++i) tmp[i] = tmp[i - 1] + cmp(sa[i - 1], sa[i]);
    for (int i = 1; i <= n; ++i) pos[sa[i]] = tmp[i] + 1;
    if (tmp[n] == n - 1) break;
  }
  
  for (int i = 1, k = 0; i <= n; ++i) { 
    if (pos[i] == n) continue;
    for (int j = sa[pos[i] + 1]; s[i + k] == s[j + k]; ) k += 1;
    lcp[i] = k;
    if (k) k -= 1;
  }
}
 
int f[N][19], lg[N];
void init() { 
  for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
  for (int i = 1; i <= n; ++i) f[i][0] = lcp[sa[i]];
  for (int j = 1; j <= 18; ++j) { 
    for (int i = 1; i <= n - (1 << j) + 1; ++i)
      f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
  }
}
inline int que(int l, int r) { 
  int j = lg[r - l + 1];
  return min(f[l][j], f[r - (1 << j) + 1][j]);
}
 
int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);
 
  cin >> s;
  n = s.size();
  
  T[0] = Hash(s, 19937, 1e9 + 7);
  T[1] = Hash(s, 10007, 1e9 + 9);
  
  s = '@' + s;
  initSA();
  init();
  
  auto count = [&](int l, int r) { 
    int sz = r - l + 1;
    l = pos[l];
    int value = 0;
    { // binarySearch left
      int le = 1, ri = l - 1, ret = l;
      while (le <= ri) { 
        int mid = (le + ri) >> 1;
        if (que(mid, l - 1) >= sz) ri = (ret = mid) - 1;
        else le = mid + 1;
      }
      
      value -= ret - 1;
    }
 
    { //binarySearch right
      int le = l, ri = n - 1, ret = l;
      while (le <= ri) { 
        int mid = (le + ri) >> 1;
        if (que(l, mid) >= sz) le = ret = mid + 1;
        else ri = mid - 1;
      }
 
      value += ret;
    }
    return value;
  };
  
  long long answer = 0;
  for (int mid1 = 1; mid1 <= n; ++mid1) { 
    for (int mid2 = mid1; mid2 <= min(n, mid1 + 1); ++mid2) { 
      if (!chk(mid1, mid2)) continue;
      
      int sz = min(mid1, n - mid2);
      int l = 0, r = sz, ret = 0;
      while (l <= r) { 
        int mid = (l + r) >> 1;
 
        if (chk(mid1 - mid, mid2 + mid)) l = (ret = mid) + 1;
        else r = mid - 1;
      }
      
      answer = max(answer, 1ll * count(mid1 - ret, mid2 + ret) * (mid2 - mid1 + 2 * ret + 1));
    }
  }
  
  cout << answer << "\n";
}

Compilation message

palindrome.cpp: In function 'void init()':
palindrome.cpp:72:48: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   72 |       f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
      |                                              ~~^~~

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

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

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 17988 KB Output is correct
2 Correct 92 ms 17988 KB Output is correct
3 Correct 133 ms 17868 KB Output is correct
4 Correct 128 ms 17996 KB Output is correct
5 Correct 151 ms 17872 KB Output is correct
6 Correct 127 ms 18000 KB Output is correct
7 Correct 113 ms 17988 KB Output is correct
8 Correct 80 ms 17988 KB Output is correct
9 Correct 106 ms 17876 KB Output is correct
10 Correct 155 ms 17996 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 36064 KB Output is correct
2 Correct 304 ms 36224 KB Output is correct
3 Correct 465 ms 36224 KB Output is correct
4 Correct 431 ms 36064 KB Output is correct
5 Correct 641 ms 36268 KB Output is correct
6 Correct 434 ms 36224 KB Output is correct
7 Correct 442 ms 36224 KB Output is correct
8 Correct 319 ms 36224 KB Output is correct
9 Correct 308 ms 36236 KB Output is correct
10 Correct 680 ms 36048 KB Output is correct
11 Correct 376 ms 36056 KB Output is correct
12 Correct 395 ms 36152 KB Output is correct