oj.uz

Submission #869639

# Submission time Handle Problem Language Result Execution time Memory
869639 2023-11-05T07:10:14 Z serifefedartar Palinilap (COI16_palinilap) C++17
100 / 100
 56 ms 25032 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 (ans != 0) {
		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(y+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++)
			ans = max(ans, res + inc[j][i] - (decr_c[i] + decr_m[i] * i));
	}
	cout << ans << "\n";
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19032 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 3 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 3 ms 21084 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8796 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 4 ms 14940 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 4 ms 21200 KB Output is correct
6 Correct 4 ms 12892 KB Output is correct
7 Correct 5 ms 23132 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 10576 KB Output is correct
2 Correct 35 ms 10624 KB Output is correct
3 Correct 37 ms 8600 KB Output is correct
4 Correct 51 ms 10536 KB Output is correct
5 Correct 51 ms 10576 KB Output is correct
6 Correct 50 ms 10572 KB Output is correct
7 Correct 53 ms 12624 KB Output is correct
8 Correct 29 ms 8536 KB Output is correct
9 Correct 52 ms 14672 KB Output is correct
10 Correct 52 ms 14672 KB Output is correct
11 Correct 35 ms 14784 KB Output is correct
12 Correct 55 ms 12624 KB Output is correct
13 Correct 54 ms 16836 KB Output is correct
14 Correct 51 ms 16768 KB Output is correct
15 Correct 51 ms 14712 KB Output is correct
16 Correct 44 ms 14668 KB Output is correct
17 Correct 56 ms 24960 KB Output is correct
18 Correct 51 ms 8524 KB Output is correct
19 Correct 55 ms 25032 KB Output is correct