oj.uz

Submission #267060

# Submission time Handle Problem Language Result Execution time Memory
267060 2020-08-15T18:42:15 Z amoo_safar Palindromes (APIO14_palindrome) C++17
41 / 100
 1000 ms 103740 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];
	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, 200); i++) Rdx[i].clear(), Rdx2[i].clear();
		for(int i = 0; i < max(n, 200); i++) Rdx[(i + st < n ? Rank[l - 1][i + st] : -1) + 1].pb(i);
		for(int j = 0; j <= max(n, 200); j++)
			for(int i : Rdx[j])
				Rdx2[Rank[l - 1][i]].pb(i);
		int po = 0;
		for(int j = 0; j <= max(n, 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 35576 KB Output is correct
2 Incorrect 34 ms 35576 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 35824 KB Output is correct
2 Correct 30 ms 35824 KB Output is correct
3 Correct 35 ms 35832 KB Output is correct
4 Correct 30 ms 35820 KB Output is correct
5 Correct 31 ms 35788 KB Output is correct
6 Correct 29 ms 35828 KB Output is correct
7 Correct 30 ms 35692 KB Output is correct
8 Correct 29 ms 35824 KB Output is correct
9 Correct 31 ms 35828 KB Output is correct
10 Correct 30 ms 35700 KB Output is correct
11 Correct 36 ms 35700 KB Output is correct
12 Correct 34 ms 35804 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 37880 KB Output is correct
2 Correct 42 ms 37740 KB Output is correct
3 Correct 46 ms 37868 KB Output is correct
4 Correct 46 ms 37744 KB Output is correct
5 Correct 39 ms 37492 KB Output is correct
6 Correct 42 ms 37500 KB Output is correct
7 Correct 42 ms 37612 KB Output is correct
8 Correct 43 ms 37552 KB Output is correct
9 Correct 46 ms 37552 KB Output is correct
10 Incorrect 45 ms 37504 KB Output isn't correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 58412 KB Output is correct
2 Correct 185 ms 56300 KB Output is correct
3 Correct 162 ms 57328 KB Output is correct
4 Correct 191 ms 55600 KB Output is correct
5 Correct 165 ms 54668 KB Output is correct
6 Correct 164 ms 55884 KB Output is correct
7 Correct 196 ms 54768 KB Output is correct
8 Correct 451 ms 54596 KB Output is correct
9 Correct 453 ms 55616 KB Output is correct
10 Correct 179 ms 55148 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 103740 KB Output is correct
2 Correct 473 ms 95136 KB Output is correct
3 Correct 523 ms 101488 KB Output is correct
4 Correct 518 ms 93700 KB Output is correct
5 Correct 526 ms 93152 KB Output is correct
6 Correct 531 ms 94008 KB Output is correct
7 Correct 498 ms 93176 KB Output is correct
8 Execution timed out 1076 ms 67072 KB Time limit exceeded
9 Halted 0 ms 0 KB -