oj.uz

Submission #1082144

# Submission time Handle Problem Language Result Execution time Memory
1082144 2024-08-30T18:38:29 Z juicy Palinilap (COI16_palinilap) C++17
100 / 100
 181 ms 25812 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
 
mt19937 rng(69420);

bool check(int x) {
  for (int i = 2; i * i <= x; ++i) {
    if (x % i == 0) {
      return 1;
    }
  }
  return 0;
}

int prime(int s, int e) {
  int x = rng() % (e - s + 1) + s;
  while (!check(x)) {
    --x;
  }
  return x;
}

using T = array<int, 3>;

const int N = 1e5 + 5;
T M = {prime(1e8, 1e9), prime(1e8, 1e9), prime(1e8, 1e9)}, B = {prime(1000, 10000), prime(1000, 10000), prime(1000, 10000)};

int n;
int cnt[N], h[3][N], rh[3][N], pw[3][N];
long long f[N];
array<long long, 26> c[N];
string s;
 
int qry(int l, int r, int *h, int M, int *pw) {
  return ((h[r] - (long long) h[l - 1] * pw[r - l + 1]) % M + M) % M;
}

array<int, 3> qry(int l, int r, int h[3][N]) {
  array<int, 3> res{};
  for (int i = 0; i < 3; ++i) {
    res[i] = qry(l, r, h[i], M[i], pw[i]);
  }
  return res;
}
 
int find(int s, int e) {
  if (s < 1 || e > n) {
    return 0;
  }
  int l = 1, r = min(s, n - e + 1), res = 0;
  while (l <= r) {
    int m = (l + r) / 2;
    if (qry(s - m + 1, s, h) == qry(n - e - m + 2, n - e + 1, rh)) {
      res = m;
      l = m + 1;
    } else {
      r = m - 1;
    }
  }
  return res;
}
 
template<class T>
void upd(int s, int e, int x, T *f) {
  f[s] += x;
  f[e + 1] -= x; 
}
 
signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
 
  cin >> s;
  n = s.size();
  for (int j = 0; j < 3; ++j) {
    pw[j][0] = 1;
    for (int i = 0; i < n; ++i) {
      pw[j][i + 1] = (long long) pw[j][i] * B[j] % M[j];
      h[j][i + 1] = ((long long) h[j][i] * B[j] + s[i] - 'a' + 1) % M[j];
    }
  }
  for (int j = 0; j < 3; ++j) {
    for (int i = n - 1; i >= 0; --i) {
      rh[j][i + 1] = ((long long) rh[j][i + 2] * B[j] + s[i] - 'a' + 1) % M[j];
    }
    reverse(rh[j] + 1, rh[j] + n + 1);
  }
  long long res = 0;
  for (int i = 1; i < n; ++i) {
    int l = find(i, i + 1);
    res += l;
    int L = i - l + 1, R = i + l;
    if (l > 0) {
      upd(i + 1, i + l, 1, cnt);
      upd(i + 1, i + l, -R - 1, f);
      upd(i - l + 1, i, -1, cnt);
      upd(i - l + 1, i, L - 1, f);
    }
    if (1 < L && R < n) {
      int l = find(L - 2, R + 2);
      c[L - 1][s[R] - 'a'] += l + 1;
      c[R + 1][s[L - 2] - 'a'] += l + 1;
    }
  }
  for (int i = 1; i <= n; ++i) {
    int l = find(i - 1, i + 1) + 1;
    res += l;
    int L = i - l + 1, R = i + l - 1;
    if (l > 1) {
      upd(L, i - 1, -1, cnt);
      upd(L, i - 1, L - 1, f);
      upd(i + 1, R, 1, cnt);
      upd(i + 1, R, -R - 1, f);
    }
    if (1 < L && R < n) {
      int l = find(L - 2, R + 2);
      c[L - 1][s[R] - 'a'] += l + 1;
      c[R + 1][s[L - 2] - 'a'] += l + 1;
    }
  }
  long long ma = 0;
  for (int i = 1; i <= n; ++i) {
    cnt[i] += cnt[i - 1];
    f[i] += f[i - 1];
    long long delta = (long long) cnt[i] * i + f[i];
    for (int j = 0; j < 26; ++j) {
      ma = max(ma, delta + c[i][j]);
    }
  }
  cout << res + ma;
  return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6748 KB Output is correct
2 Correct 5 ms 6744 KB Output is correct
3 Correct 6 ms 6924 KB Output is correct
4 Correct 4 ms 6748 KB Output is correct
5 Correct 5 ms 6916 KB Output is correct
6 Correct 7 ms 6908 KB Output is correct
7 Correct 7 ms 6744 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 25640 KB Output is correct
2 Correct 114 ms 25680 KB Output is correct
3 Correct 118 ms 25680 KB Output is correct
4 Correct 174 ms 25680 KB Output is correct
5 Correct 173 ms 25684 KB Output is correct
6 Correct 168 ms 25680 KB Output is correct
7 Correct 173 ms 25684 KB Output is correct
8 Correct 89 ms 7004 KB Output is correct
9 Correct 168 ms 25556 KB Output is correct
10 Correct 167 ms 25684 KB Output is correct
11 Correct 113 ms 25680 KB Output is correct
12 Correct 181 ms 25812 KB Output is correct
13 Correct 167 ms 25812 KB Output is correct
14 Correct 171 ms 25680 KB Output is correct
15 Correct 180 ms 25680 KB Output is correct
16 Correct 149 ms 25684 KB Output is correct
17 Correct 162 ms 25684 KB Output is correct
18 Correct 173 ms 25620 KB Output is correct
19 Correct 169 ms 25680 KB Output is correct