oj.uz

Submission #869416

# Submission time Handle Problem Language Result Execution time Memory
869416 2023-11-04T09:42:38 Z serifefedartar Palinilap (COI16_palinilap) C++17
0 / 100
 59 ms 12892 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;

const ll P = 31;
string s;
int decr[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, int v) {
	decr[l] += v;
	decr[r+1] -= v;
}

void calc(int x, int y) {
	int mx_len = min(x, n-y+1);
	int L = 1;
	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;
	}

	if (ans < 1)
		return ;
	res += ans; 

	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;
	}

	if (mx_len == ans)
		_ans = ans;
	
	int l = x - ans + 1;
	int r = x + ans - 1;
	if (x != y) {
		f(l, r, 1);
		int L = l-1;
		int R = r+1;
		if (L != 0 && R != n+1) {
			inc[s[L] - 'a'][R] += _ans - ans;
			inc[s[R] - 'a'][L] += _ans - ans;
		}
	} else {
		f(l, x-1, 1);
		f(x+1, r, 1);
		int L = l-1;
		int R = r+1;
		if (L != 0 && R != n+1) {
			inc[s[L] - 'a'][R] += _ans - ans;
			inc[s[R] - 'a'][L] += _ans - ans;
		}
	}
}

int 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[i] += decr[i-1];

	ll ans = res;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 26; j++)
			ans = max(ans, res + inc[j][i] - decr[i]);
	}
	cout << ans << "\n";
}

Subtask #1
0 / 17.0

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

Subtask #2
0 / 37.0

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

Subtask #3
0 / 46.0

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