oj.uz

Submission #1082085

# Submission time Handle Problem Language Result Execution time Memory
1082085 2024-08-30T16:57:45 Z juicy Palinilap (COI16_palinilap) C++17
0 / 100
 21 ms 13660 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

using ull = unsigned long long;

const int N = 1e5 + 5;

int n;
int cnt[N];
long long f[N];
array<int, 26> c[N];
string s;
ull h[N], pw[N];

ull qry(int l, int r) {
  return h[r] - h[l - 1] * pw[r - l + 1];
}

int find(int s, int e) {
  if (s < 1 || e > n) {
    return 0;
  }
  int l = 0, r = min(s, n - e + 1), res = 0;
  while (l <= r) {
    int m = (l + r) / 2;
    if (qry(s - m + 1, s) == qry(e, e + m - 1)) {
      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; 
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> s;
  n = s.size();
  pw[0] = 1;
  for (int i = 0; i < n; ++i) {
    pw[i + 1] = pw[i] * 31;
    h[i + 1] = h[i] * 31 + s[i] - 'a' + 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 = 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
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4700 KB Output is correct
2 Incorrect 1 ms 4564 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 13660 KB Output isn't correct
2 Halted 0 ms 0 KB -