oj.uz

Submission #813466

# Submission time Handle Problem Language Result Execution time Memory
813466 2023-08-07T18:24:50 Z Divane Palinilap (COI16_palinilap) C++14
100 / 100
 86 ms 31420 KB 
/* In the name of GOD */

#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second 
#define mk make_pair
typedef long long ll;
typedef long double ld;
#define int long long
typedef pair <int, int> pii;
const int N = 200012, M = 1000000007, B = 373;
int a[N], b[N];
int ps[N];
int pe[N];
int A[26];
int hr[N];
int hl[N];
int p[N];
int n;
vector <int> st[N], e[N];
int sp[N], sn[N];

int getL (int l, int r) {
	l = n - 1 - l;
	r = n - 1 - r;
	return (((hl[r] - hl[l - 1] * p[r - l + 1]) % M) + M) % M;
}

int getR (int l, int r) {
	return (((hr[r] - hr[l - 1] * p[r - l + 1]) % M) + M) % M;
}

int32_t main () {
	p[0] = 1;
	for (int i = 1; i < N; i++) {
		p[i] = p[i - 1] * B;
		p[i] %= M;
	}
	string s, t;
	cin >> t;
	s = "#3#4#";
	for (char c : t) {
		s += c;
		s += '#';
	}
	s += "2#1#";
	n = (int)s.size();
	int H = 0;
	for (int i = 0; i < n; i++) {
		H *= B;
		H += s[i];
		H %= M;
		hr[i] = H;
	}
	reverse(s.begin(), s.end());
	H = 0;
	for (int i = 0; i < n; i++) {
		H *= B;
		H += s[i];
		H %= M;
		hl[i] = H;
	}
	reverse(s.begin(), s.end());
	int ans = 0;
	for (int i = 5; i < n - 5; i++) {
		int l = 1, r = min(i, n - i - 1);
		while (r - l > 1) {
			int mid = (l + r) >> 1;
			if (getR (i, i + mid - 1) == getL(i, i - mid + 1))
				l = mid;
			else
				r = mid;
		}
		st[i - l].push_back(i);
		e[i + l].push_back(i);
		ans += (l / 2);
		a[i] = l / 2;
		if (l != 1) {
			ps [i + l - 1]--;
			ps [i]++;
			sn [i + l - 1]--;
			sn [i]++;
			ps [i - 1]++;
			ps [i - l]--;
			sp [i - 1]++;
			sp [i - l]--;
		}
		int ol = l + 1;
		l = 0, r = min(n - (i + ol) - 1, i - ol);
		while (r - l > 1) {
			int mid = (l + r) >> 1;
			if (getR (i + ol, i + ol + mid - 1) == getL(i - ol, i - ol - mid + 1))
				l = mid;
			else
				r = mid;
		}
		b[i] = l;
	}
	for (int i = n - 1; i >= 0; i--)
		ps[i] = ps[i + 1] + ps[i];
	for (int i = n - 1; i >= 0; i--)
		sp[i] = sp[i + 1] + sp[i];
	for (int i = n - 1; i >= 0; i--)
		sn[i] = sn[i + 1] + sn[i];
	int pps = 0;
	int mx = ans + 1;
	for (int i = 0; i < n; i++) {
		if (i % 2)
			pps += sp[i];
		if (i >= 5 && i < n - 5 && i % 2) {
			int ANS = ans;
			ANS -= pps;
			ANS += a[i];
			for (int wef : st[i]) {
				char c = s[wef + (wef - i)];
				A[c - 'a'] += b[wef] / 2 + 1;
			}
			for (int wef : e[i]) {
				char c = s[wef - (i - wef)];
				A[c - 'a'] += b[wef] / 2 + 1;
			}
			int MX = 0;
			for (int i = 0; i < 26; i++) {
				MX = max(MX, A[i]);
				A[i] = 0;
			}
			mx = max(mx, MX + ANS);
		}
		if (i % 2)
			pps += sn[i];
	}
	cout << mx - 1 << '\n';
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11220 KB Output is correct
2 Correct 8 ms 11348 KB Output is correct
3 Correct 7 ms 11220 KB Output is correct
4 Correct 6 ms 11280 KB Output is correct
5 Correct 6 ms 11276 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12244 KB Output is correct
2 Correct 8 ms 12244 KB Output is correct
3 Correct 9 ms 12172 KB Output is correct
4 Correct 8 ms 11784 KB Output is correct
5 Correct 10 ms 11988 KB Output is correct
6 Correct 9 ms 12244 KB Output is correct
7 Correct 9 ms 12164 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 29724 KB Output is correct
2 Correct 52 ms 30368 KB Output is correct
3 Correct 52 ms 30416 KB Output is correct
4 Correct 73 ms 29736 KB Output is correct
5 Correct 75 ms 29804 KB Output is correct
6 Correct 73 ms 29704 KB Output is correct
7 Correct 73 ms 29840 KB Output is correct
8 Correct 46 ms 30352 KB Output is correct
9 Correct 86 ms 29784 KB Output is correct
10 Correct 74 ms 29704 KB Output is correct
11 Correct 50 ms 30400 KB Output is correct
12 Correct 70 ms 31420 KB Output is correct
13 Correct 79 ms 29928 KB Output is correct
14 Correct 73 ms 29652 KB Output is correct
15 Correct 75 ms 29764 KB Output is correct
16 Correct 69 ms 30336 KB Output is correct
17 Correct 68 ms 29016 KB Output is correct
18 Correct 73 ms 28984 KB Output is correct
19 Correct 67 ms 28984 KB Output is correct