oj.uz

Submission #617411

# Submission time Handle Problem Language Result Execution time Memory
617411 2022-08-01T11:14:00 Z HappyPacMan Palinilap (COI16_palinilap) C++14
100 / 100
 55 ms 48804 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e5 + 13;
const int mod[] = {1000000007,998244353};
int pow26[2][maxn],hprefix[2][18][maxn],hsuffix[2][18][maxn];
ll addi[26][maxn],odd[maxn],even[maxn],prefix[maxn];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	string s;
	cin >> s;
	int n = s.size();

	// Precompute 26^k
	pow26[0][0] = pow26[1][0] = 1;
	for(int i=0;i<n;i++){
		pow26[0][i+1] = (26ll*pow26[0][i])%mod[0];
		pow26[1][i+1] = (26ll*pow26[1][i])%mod[1];
	}

	// Precompute Hashing and Sparse Table
	for(int i=0;i<n;i++){
		hprefix[0][0][i] = hprefix[1][0][i] = hsuffix[0][0][i] = hsuffix[1][0][i] = s[i]-'a';
	}
	for(int i=1;i<18;i++){
		for(int j=0;j+(1<<i)<=n;j++){
			hprefix[0][i][j] = (hprefix[0][i-1][j]+1ll*pow26[0][1<<(i-1)]*hprefix[0][i-1][j+(1<<(i-1))])%mod[0];
			hprefix[1][i][j] = (hprefix[1][i-1][j]+1ll*pow26[1][1<<(i-1)]*hprefix[1][i-1][j+(1<<(i-1))])%mod[1];
		}
		for(int j=n-1;j-(1<<i)>=-1;j--){
			hsuffix[0][i][j] = (hsuffix[0][i-1][j]+1ll*pow26[0][1<<(i-1)]*hsuffix[0][i-1][j-(1<<(i-1))])%mod[0];
			hsuffix[1][i][j] = (hsuffix[1][i-1][j]+1ll*pow26[1][1<<(i-1)]*hsuffix[1][i-1][j-(1<<(i-1))])%mod[1];
		}
	}

	for(int i=0;i<n-1;i++){
		if(i > 0){
			int z = 0;
			for(int j=17;j>=0;j--){
				if(i-1-z-(1<<j) >= -1 && i+1+z+(1<<j) <= n && hsuffix[0][j][i-1-z] == hprefix[0][j][i+1+z] && hsuffix[1][j][i-1-z] == hprefix[1][j][i+1+z]){
					z += (1<<j);
				}
			}
			odd[i] = z;
			prefix[i-z]--;
			prefix[i]++;
			prefix[i+2]++;
			prefix[i+z+2]--;
			// cout << i << " " << z << " -> " << i-z+1 << ' ' << i+1 << ' ' << i+z+1 << '\n';
			if(i-2-z >= -1 && i+2+z <= n){
				int l = i-1-z, r = i+1+z, v = 1;
				for(int j=17;j>=0;j--){
					if(l-v-(1<<j) >= -1 && r+v+(1<<j) <= n && hsuffix[0][j][l-v] == hprefix[0][j][r+v] && hsuffix[1][j][l-v] == hprefix[1][j][r+v]){
						v += (1<<j);
					}
				}
				addi[s[l]-'a'][r] += v;
				addi[s[r]-'a'][l] += v;
				// cout << i << " " << z << " -> " << " go to " << v << "\n";
			}
		}
		int z = 0;
		for(int j=17;j>=0;j--){
			if(i-z-(1<<j) >= -1 && i+1+z+(1<<j) <= n && hsuffix[0][j][i-z] == hprefix[0][j][i+1+z] && hsuffix[1][j][i-z] == hprefix[1][j][i+1+z]){
				z += (1<<j);
			}
		}
		even[i] = z;
		prefix[i-z+1]--;
		prefix[i+1]++;
		prefix[i+2]++;
		prefix[i+z+2]--;	
		// cout << i << ' ' << z << " -> " << i-z+1 << ' ' << i+1 << ' ' << i+2 << ' ' << i+z+2 << '\n';
		if(i-1-z >= -1 && i+2+z <= n){
			int l = i-z, r = i+1+z, v = 1;
			for(int j=17;j>=0;j--){
				if(l-v-(1<<j) >= -1 && r+v+(1<<j) <= n && hsuffix[0][j][l-v] == hprefix[0][j][r+v] && hsuffix[1][j][l-v] == hprefix[1][j][r+v]){
					v += (1<<j);
				}
			}
			addi[s[l]-'a'][r] += v;
			addi[s[r]-'a'][l] += v;
		}
	}
	for(int i=1;i<=n;i++){
		prefix[i] += prefix[i-1];
	}
	/*
	for(int i=0;i<=n;i++){
		cout << prefix[i] << " ";
	}
	cout << "\n";
	*/
	for(int i=1;i<=n;i++){
		prefix[i] += prefix[i-1];
	}
	/*
	for(int i=0;i<=n;i++){
		cout << prefix[i] << " ";
	}
	cout << "\n";
	*/
	ll tot = 0;
	for(int i=0;i<n-1;i++){
		tot += odd[i]+even[i];
	}
	for(int i=0;i<=n;i++){
		prefix[i] += tot;
	}
	ll res = 0;
	for(int i=0;i<n-1;i++){
		res += odd[i] + even[i];
	}
	/*
	for(int i=0;i<=n;i++){
		cout << prefix[i] << " ";
	}
	cout << "\n";
	*/
	for(int i=0;i<n;i++){
		ll mx = 0;
		for(int j=0;j<26;j++){
			// cout << addi[j][i] << " ";
			mx = max(mx,addi[j][i]);
		}
		// cout << " : " << mx << " " << n << "\n";
		res = max(res,mx+prefix[i]+odd[i]);
	}
	cout << res + n << '\n';
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1748 KB Output is correct
2 Correct 2 ms 1748 KB Output is correct
3 Correct 3 ms 1748 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 2 ms 1748 KB Output is correct
6 Correct 4 ms 1876 KB Output is correct
7 Correct 3 ms 2772 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 30040 KB Output is correct
2 Correct 49 ms 29164 KB Output is correct
3 Correct 43 ms 29288 KB Output is correct
4 Correct 44 ms 30796 KB Output is correct
5 Correct 42 ms 30920 KB Output is correct
6 Correct 45 ms 30756 KB Output is correct
7 Correct 54 ms 30768 KB Output is correct
8 Correct 40 ms 28512 KB Output is correct
9 Correct 45 ms 30760 KB Output is correct
10 Correct 43 ms 30736 KB Output is correct
11 Correct 44 ms 29228 KB Output is correct
12 Correct 48 ms 30720 KB Output is correct
13 Correct 51 ms 30848 KB Output is correct
14 Correct 45 ms 31556 KB Output is correct
15 Correct 45 ms 31544 KB Output is correct
16 Correct 55 ms 29984 KB Output is correct
17 Correct 50 ms 47956 KB Output is correct
18 Correct 49 ms 29992 KB Output is correct
19 Correct 48 ms 48804 KB Output is correct