oj.uz

Submission #869482

# Submission time Handle Problem Language Result Execution time Memory
869482 2023-11-04T12:21:24 Z serifefedartar Palinilap (COI16_palinilap) C++17
0 / 100
 54 ms 19036 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+9;
const ll LOGN = 30; 
const ll MAXN = 1e5 + 100;
const ll MULT = 1e9;
#define int long long

const ll P = 31;
string s;
int decr_c[MAXN], decr_m[MAXN], inc[26][MAXN], n;
ll hashes[MAXN], hashes_rev[MAXN], pw[MAXN], res = 0;
ll _hash(int x, int len, bool rev) {
	if (rev == 0) {
		int r = x + len - 1;
		ll res = (hashes[r] - (hashes[x-1] * pw[r-x+1]) % MOD + MOD) % MOD;
		return res;
	} else {
		int l = x - len + 1;
		ll res = (hashes_rev[l] - (hashes_rev[x+1] * pw[x+1-l]) % MOD + MOD) % MOD;
		return res;
	}
}

void f(int l, int r, bool rev) {
	if (l > r)
		return ;
	int c, m;
	if (rev == 0) {
		c = -(l - 1);
		m = 1;
	} else {
		c = r + 1;
		m = -1;
	}

	decr_c[l] += c;
	decr_c[r+1] -= c;
	decr_m[l] += m;
	decr_m[r+1] -= m;
}

void calc(int x, int y) {
	int mx_len = min(x, n-y+1);
	int L = 0;
	int R = mx_len;
	int ans = 0;
	while (R >= L) {
		int mid = L + (R-L)/2;
		if (_hash(x, mid, 1) == _hash(y, mid, 0)) {
			ans = mid;
			L = mid + 1;
		} else
			R = mid - 1;
	}

	res += ans;

	int l = x - ans + 1;
	int r = y + ans - 1;
	if (x != y) {
		f(l, x, 0);
		f(y, r, 1);
	} else {
		f(l, x-1, 0);
		f(x+1, r, 1);
	}

	if (ans != mx_len) {
		int _L = ans + 2;
		int _R = mx_len;
		int _ans = ans + 1;
		while (_R >= _L) {
			int mid = _L + (_R - _L) / 2;
			if (_hash(x-ans-1, mid - ans - 1, 1) == _hash(x+ans+1, mid - ans - 1, 0)) {
				_ans = mid;
				_L = mid + 1;
			} else
				_R = mid - 1;
		}

		L = l-1;
		R = r+1;
		inc[s[L] - 'a'][R] += _ans - ans;
		inc[s[R] - 'a'][L] += _ans - ans;
	}
}

signed main() {
	fast
	cin >> s;
	n = s.length();
	s = "#" + s;
	pw[0] = 1;
	for (int i = 1; i < MAXN; i++)
		pw[i] = (pw[i-1] * P) % MOD;
	for (int i = 1; i <= n; i++)
		hashes[i] = (hashes[i-1] * P + (s[i] - 'a' + 1)) % MOD;		
	for (int i = n; i >= 1; i--)
		hashes_rev[i] = (hashes_rev[i+1] * P + (s[i] - 'a' + 1)) % MOD;

	for (int i = 1; i <= n; i++) {
		calc(i, i);
		if (i != 1)
			calc(i-1, i);
	}

	for (int i = 1; i <= n; i++) {
		decr_c[i] += decr_c[i-1];
		decr_m[i] += decr_m[i-1];
	}

	ll ans = res;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 26; j++) {
			if (s[i] - 'a' != j)
				ans = max(ans, res + inc[j][i] - (decr_c[i] + decr_m[i] * i));
		}
	}
	cout << ans << "\n";
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19036 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Incorrect 2 ms 8796 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8792 KB Output is correct
2 Correct 5 ms 10844 KB Output is correct
3 Incorrect 5 ms 15004 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

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