Submission #869482

#	Time	Username	Problem	Language	Result	Execution time	Memory
869482		serifefedartar	Palinilap (COI16_palinilap)	C++17	0 / 100	54 ms	19036 KiB

palinilap

#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
• Subtask 2: 0 / 37
• Subtask 3: 0 / 46