oj.uz

Submission #267070

# Submission time Handle Problem Language Result Execution time Memory
267070 2020-08-15T19:02:00 Z amoo_safar Palindromes (APIO14_palindrome) C++17
49 / 100
 1000 ms 103784 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<pll, pll> node;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
const ll Mod = 1e9 + 9;
const int Maxn = 3e5 + 10;
const int Maxk = 60;
const ll Inf = 2242545357980376863LL;
const ll Log = 20;
const ll Base = 998244353;
 
int Rank[Log][Maxn], n;
int idx[Maxn];
ll ph[Maxn], phr[Maxn], pw[Maxn];
pii a[Maxn];

vector<int> Rdx[Maxn];
vector<int> Rdx2[Maxn];

str s;
 
ll get(int l, int r){
	return (ph[r] - (ph[l]*pw[r - l] % Mod) + Mod) % Mod;
}
ll get_rev(int l, int r){
	return (phr[l] - (phr[r]*pw[r - l] % Mod) + Mod) % Mod;
}
 
int pal_range(int l, int r){
	int L = 0, R = min(n - r, l) + 1, mid;
	
	//int res = 0;
	//for(int i = 0; i < R - 1; i ++) if(s[l - 1 - i] != s[r + i]) return i;
	//return R - 1;
	
	while(L + 1 < R){
		mid = (L + R) >> 1;
		if(get(l - mid, l) == get_rev(r, r + mid)) L = mid;
		else R = mid;
	}
	return L;
}
 
int pal[Maxn];
 
 
int eq_range(int l1, int l2){
	int L = 0, R = min(n - l1, n - l2) + 1, mid;
	//for(int i = 0; i + 1 < R; i++) if(s[i + l1] != s[i + l2]) return i;
	//return R - 1;
	while(L + 1 < R){
		mid = (L + R) >> 1;
		if(get(l1, l1 + mid) == get(l2, l2 + mid)) L = mid;
		else R = mid;
	}
	return L;
}
int eq[Maxn];
 
 
int par[Maxn], sz[Maxn];
vector<int> Merge[Maxn];
vector<int> On[Maxn];
 
int get_par(int u){
	if(par[u] == u) return u;
	return par[u] = get_par(par[u]);
}
void merge(int u, int v){
	u = get_par(u); v = get_par(v);
	sz[u] += sz[v];
	par[v] = par[u];
}
 
int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	pw[0] = 1;
	for(int i = 1; i < Maxn; i++) pw[i] = (pw[i - 1] * Base) % Mod;
	
	cin >> s;
	n = s.size();
	
	ph[0] = 0;
	for(int i = 1; i <= n; i++) ph[i] = (ph[i - 1] * Base + s[i - 1]) % Mod;
	phr[n] = 0;
	for(int i = n - 1; i >= 0; i--) phr[i] = (phr[i + 1] * Base + s[i]) % Mod;
	//cerr << get(0, 2) << " " << get(n-2, n) << '\n';
	
	for(int i = 0; i < n; i++) Rank[0][i] = s[i]-'a';
	int st;
	for(int l = 1; l < Log; l++){
		st = (1 << (l - 1));
		/*
		for(int i = 0; i < n; i++){
			a[i].F = Rank[l - 1][i];
			a[i].S = (i + st < n ? Rank[l - 1][i + st] : -1); 
		}
		*/
		for(int i = 0; i <= max(n + 1, 200); i++) Rdx[i].clear(), Rdx2[i].clear();
		for(int i = 0; i < n; i++) Rdx[(i + st < n ? Rank[l - 1][i + st] : -1) + 1].pb(i);
		for(int j = 0; j <= max(n + 1, 200); j++)
			for(int i : Rdx[j])
				Rdx2[Rank[l - 1][i]].pb(i);
		int po = 0;
		for(int j = 0; j <= max(n + 1, 200); j++)
			for(int i : Rdx2[j])
				Rank[l][i] = po ++;
		/*
		for(int i = 0; i < n; i++)
			Rank[l][i] = lower_bound(a, a + n, pii(Rank[l - 1][i], (i + st < n ? Rank[l - 1][i + st] : -1) )) - a;
		*/
	}
	for(int i = 0; i < n; i++) idx[Rank[Log - 1][i]] = i;
	
	for(int i = 0; i < n - 1; i++) eq[i] = eq_range(idx[i], idx[i + 1]);
	for(int i = 0; i < n - 1; i++) Merge[eq[i]].pb(i);
	
	ll ans = 0;
	
	for(int i = 0; i < n; i++) pal[i] = pal_range(i + 1, i);
	for(int i = 0; i < n; i++) On[pal[i]].pb(Rank[Log - 1][i]);
	
	
	iota(par, par + Maxn, 0);
	fill(sz, sz + Maxn, 0);
	int mx = 0;
	for(int x = n + 1; x >= 1; x--){
		for(auto y : Merge[x]){
			merge(y, y + 1);
			mx = max(mx, sz[get_par(y)]);
		}
		for(auto y : On[x]){
			sz[get_par(y)] ++;
			mx = max(mx, sz[get_par(y)]);
		}
		ans = max(ans, 1LL * mx * (x + x - 1));
	}
	
	for(int i = 0; i < n; i++) pal[i] = pal_range(i, i);
	for(int i = 0; i < Maxn; i++) On[i].clear();
	for(int i = 0; i < Maxn; i++) On[pal[i]].pb(Rank[Log - 1][i]);
	
	iota(par, par + Maxn, 0);
	fill(sz, sz + Maxn, 0);
	mx = 0;
	for(int x = n + 1; x >= 1; x--){
		for(auto y : Merge[x]){
			merge(y, y + 1);
			mx = max(mx, sz[get_par(y)]);
		}
		for(auto y : On[x]){
			sz[get_par(y)] ++;
			mx = max(mx, sz[get_par(y)]);
		}
		ans = max(ans, 1LL * mx * (x + x));
	}
	
	cout << ans << '\n';;
	return 0;
}
 
/*
abacaba
 
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 35576 KB Output is correct
2 Correct 29 ms 35576 KB Output is correct
3 Correct 28 ms 35576 KB Output is correct
4 Correct 30 ms 35576 KB Output is correct
5 Correct 29 ms 35576 KB Output is correct
6 Correct 30 ms 35568 KB Output is correct
7 Correct 28 ms 35576 KB Output is correct
8 Correct 28 ms 35576 KB Output is correct
9 Correct 31 ms 35568 KB Output is correct
10 Correct 27 ms 35572 KB Output is correct
11 Correct 27 ms 35572 KB Output is correct
12 Correct 27 ms 35576 KB Output is correct
13 Correct 30 ms 35576 KB Output is correct
14 Correct 27 ms 35576 KB Output is correct
15 Correct 27 ms 35576 KB Output is correct
16 Correct 27 ms 35568 KB Output is correct
17 Correct 32 ms 35568 KB Output is correct
18 Correct 27 ms 35576 KB Output is correct
19 Correct 27 ms 35568 KB Output is correct
20 Correct 30 ms 35568 KB Output is correct
21 Correct 31 ms 35568 KB Output is correct
22 Correct 28 ms 35576 KB Output is correct
23 Correct 30 ms 35568 KB Output is correct
24 Correct 28 ms 35576 KB Output is correct
25 Correct 28 ms 35576 KB Output is correct
26 Correct 28 ms 35576 KB Output is correct
27 Correct 28 ms 35576 KB Output is correct
28 Correct 27 ms 35576 KB Output is correct
29 Correct 27 ms 35564 KB Output is correct
30 Correct 29 ms 35576 KB Output is correct
31 Correct 27 ms 35576 KB Output is correct
32 Correct 29 ms 35576 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 35832 KB Output is correct
2 Correct 31 ms 35824 KB Output is correct
3 Correct 30 ms 35824 KB Output is correct
4 Correct 30 ms 35820 KB Output is correct
5 Correct 31 ms 35824 KB Output is correct
6 Correct 28 ms 35828 KB Output is correct
7 Correct 28 ms 35700 KB Output is correct
8 Correct 32 ms 35832 KB Output is correct
9 Correct 31 ms 35828 KB Output is correct
10 Correct 29 ms 35828 KB Output is correct
11 Correct 28 ms 35820 KB Output is correct
12 Correct 28 ms 35828 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 37872 KB Output is correct
2 Correct 42 ms 37748 KB Output is correct
3 Correct 39 ms 37868 KB Output is correct
4 Correct 39 ms 37748 KB Output is correct
5 Correct 37 ms 37492 KB Output is correct
6 Correct 38 ms 37492 KB Output is correct
7 Correct 40 ms 37612 KB Output is correct
8 Correct 50 ms 37552 KB Output is correct
9 Correct 49 ms 37680 KB Output is correct
10 Incorrect 41 ms 37504 KB Output isn't correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 58540 KB Output is correct
2 Correct 165 ms 56428 KB Output is correct
3 Correct 175 ms 57468 KB Output is correct
4 Correct 157 ms 55856 KB Output is correct
5 Correct 161 ms 54796 KB Output is correct
6 Correct 169 ms 55884 KB Output is correct
7 Correct 161 ms 54772 KB Output is correct
8 Correct 415 ms 54560 KB Output is correct
9 Correct 337 ms 55756 KB Output is correct
10 Correct 180 ms 55148 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 103784 KB Output is correct
2 Correct 460 ms 95288 KB Output is correct
3 Correct 443 ms 101616 KB Output is correct
4 Correct 459 ms 93700 KB Output is correct
5 Correct 495 ms 93328 KB Output is correct
6 Correct 477 ms 94132 KB Output is correct
7 Correct 478 ms 93176 KB Output is correct
8 Execution timed out 1095 ms 71908 KB Time limit exceeded
9 Halted 0 ms 0 KB -