oj.uz

Submission #138866

# Submission time Handle Problem Language Result Execution time Memory
138866 2019-07-30T15:26:55 Z parsa_mobed Palinilap (COI16_palinilap) C++14
100 / 100
 273 ms 80504 KB 
#include <bits/stdc++.h>

using namespace std;
#define int long long
const int N = 1e5 + 10, B = 101, MOD = 1e9 + 7, X = 11;
int Hash[N], revHash[N], P[N], s[N], q[N], Q1[N], Q2[N], ps1[N], ps2[N], n, cnt = 0;
vector <int> V[N][26];

//functions
int mod(int a) {return (a % MOD + MOD) % MOD;}

int HASH(int l, int r)
{
	if (l == 0) return Hash[r];
	return mod(Hash[r] - Hash[l - 1] * P[r - l + 1]);
}

int REVHASH(int l, int r)
{
	return mod(revHash[l] - revHash[r + 1] * P[r - l + 1]);
}

int val(int l1, int r1, int l2, int r2)
{
	if (l1 < 0 || l2 < 0 || r1 >= n || r2 >= n) return 0;
   return (REVHASH(l1, r1) == HASH(l2, r2));
}

int BS(int l1, int l2)
{
	if (l1 < 0 || l2 < 0 || l1 >= n || l2 >= n) return -1;
	if (s[l1] != s[l2]) return -1;
	int L = 0, R = min(l1, n - l2 - 1) + 1;
	while (R - L > 1) {
		int md = (R + L) / 2;
		if (val(l1 - md, l1, l2, l2 + md)) L = md;
		else R = md;
	}
	return L;
}
//end


int32_t main()
{
	//preprocess
	P[0] = 1;
	for (int i = 1; i < N; i ++) P[i] = (P[i - 1] * B) % MOD;
   //Input
	string st; cin >> st;
	n = st.size();
	for (int i = 0; i < n; i ++) s[i] = st[i] - 'a';
	//set Hash
	Hash[0] = s[0] + X;
	for (int i = 1; i < n; i ++) {
		Hash[i] = (Hash[i - 1] * B + s[i] + X) % MOD;
	}
	revHash[n - 1] = s[n - 1] + X;
	for (int i = n - 2; i >= 0; i --) {
		revHash[i] = (revHash[i + 1] * B + s[i] + X) % MOD;
	}
	//end
   for (int i = 0; i < n; i ++) {
		int t = BS(i, i);
		if (i - t - 1 >= 0) V[i - t - 1][s[i + t + 1]].push_back(i + t + 1);
		if (i + t + 1 < n) V[i + t + 1][s[i - t - 1]].push_back(i - t - 1);
		if (t != 0) {
			ps1[i]--;
			ps1[i + t]++;
			Q1[i] = -t;
		}
		if (t != 0) {
			ps2[i]--;
			ps2[i - t]++;
			Q2[i] = -t;
		}
		cnt += t + 1;
	}
	for (int i = 0; i < n - 1; i ++) {
		int t = BS(i, i + 1);
		if (i - t - 1 >= 0) V[i - t - 1][s[i + t + 2]].push_back(i + t + 2);
		if (i + t + 2 < n) V[i + t + 2][s[i - t - 1]].push_back(i - t - 1);
		if (t == -1) continue;
		ps1[i]--;
		ps1[i + t + 1]++;
		Q1[i] += -(t + 1);
		ps2[i + 1]--;
		ps2[i - t]++;
		Q2[i + 1] += -(t + 1);
		cnt += t + 1;
	}
	for (int i = n - 2; i >= 0; i --) ps1[i] += ps1[i + 1];
	for (int i = 1; i < n; i ++) ps2[i] += ps2[i - 1];
	Q1[n - 1] += ps1[n - 1];
	for (int i = n - 2; i >= 0; i --) Q1[i] += ps1[i] + Q1[i + 1];
	Q2[0] += ps2[0];
	for (int i = 1; i < n; i ++) Q2[i] += ps2[i] + Q2[i - 1];
	for (int i = 0; i < n; i ++) q[i] = Q1[i] + Q2[i];
	//find ans
	int ans = cnt;
	for (int i = 0; i < n; i ++) for (int c = 0; c < 26; c ++){
		int val = 0;
		for (auto j : V[i][c]) {
			if (j < 0 || j >= n) continue ;
			if (i < j) val += BS(i - 1, j + 1) + 2;
			else val += BS(j - 1, i + 1) + 2;
		}
		ans = max(ans, cnt + val - q[i]);
	}
   //Output
   cout << ans << "\n";
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 62200 KB Output is correct
2 Correct 60 ms 62328 KB Output is correct
3 Correct 61 ms 62204 KB Output is correct
4 Correct 60 ms 62268 KB Output is correct
5 Correct 60 ms 62200 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 62840 KB Output is correct
2 Correct 65 ms 62888 KB Output is correct
3 Correct 67 ms 62968 KB Output is correct
4 Correct 64 ms 62712 KB Output is correct
5 Correct 67 ms 62840 KB Output is correct
6 Correct 67 ms 62924 KB Output is correct
7 Correct 66 ms 63096 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 74592 KB Output is correct
2 Correct 200 ms 73388 KB Output is correct
3 Correct 190 ms 72556 KB Output is correct
4 Correct 245 ms 75540 KB Output is correct
5 Correct 233 ms 75636 KB Output is correct
6 Correct 258 ms 75584 KB Output is correct
7 Correct 239 ms 75604 KB Output is correct
8 Correct 183 ms 71800 KB Output is correct
9 Correct 236 ms 75568 KB Output is correct
10 Correct 239 ms 75636 KB Output is correct
11 Correct 208 ms 73496 KB Output is correct
12 Correct 199 ms 75788 KB Output is correct
13 Correct 273 ms 74360 KB Output is correct
14 Correct 224 ms 76280 KB Output is correct
15 Correct 234 ms 76152 KB Output is correct
16 Correct 255 ms 76520 KB Output is correct
17 Correct 199 ms 80476 KB Output is correct
18 Correct 240 ms 74020 KB Output is correct
19 Correct 242 ms 80504 KB Output is correct