oj.uz

Submission #162351

# Submission time Handle Problem Language Result Execution time Memory
162351 2019-11-07T16:21:44 Z amoo_safar Palindromes (APIO14_palindrome) C++14
73 / 100
 1000 ms 69948 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 = 1000000009LL;
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];
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); 
		}
		sort(a, a + n);
		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;
	return 0;
}

/*
abacaba

*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 21488 KB Output is correct
2 Correct 28 ms 21484 KB Output is correct
3 Correct 30 ms 21504 KB Output is correct
4 Correct 29 ms 21488 KB Output is correct
5 Correct 28 ms 21488 KB Output is correct
6 Correct 29 ms 21488 KB Output is correct
7 Correct 30 ms 21420 KB Output is correct
8 Correct 30 ms 21484 KB Output is correct
9 Correct 28 ms 21484 KB Output is correct
10 Correct 30 ms 21484 KB Output is correct
11 Correct 28 ms 21488 KB Output is correct
12 Correct 29 ms 21484 KB Output is correct
13 Correct 28 ms 21488 KB Output is correct
14 Correct 28 ms 21484 KB Output is correct
15 Correct 55 ms 21480 KB Output is correct
16 Correct 29 ms 21520 KB Output is correct
17 Correct 60 ms 21472 KB Output is correct
18 Correct 56 ms 21616 KB Output is correct
19 Correct 62 ms 21488 KB Output is correct
20 Correct 28 ms 21612 KB Output is correct
21 Correct 29 ms 21532 KB Output is correct
22 Correct 28 ms 21488 KB Output is correct
23 Correct 28 ms 21484 KB Output is correct
24 Correct 28 ms 21488 KB Output is correct
25 Correct 28 ms 21484 KB Output is correct
26 Correct 28 ms 21488 KB Output is correct
27 Correct 29 ms 21616 KB Output is correct
28 Correct 28 ms 21488 KB Output is correct
29 Correct 28 ms 21488 KB Output is correct
30 Correct 28 ms 21492 KB Output is correct
31 Correct 29 ms 21540 KB Output is correct
32 Correct 31 ms 21488 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 21632 KB Output is correct
2 Correct 32 ms 21616 KB Output is correct
3 Correct 29 ms 21612 KB Output is correct
4 Correct 30 ms 21616 KB Output is correct
5 Correct 30 ms 21584 KB Output is correct
6 Correct 30 ms 21752 KB Output is correct
7 Correct 31 ms 21616 KB Output is correct
8 Correct 29 ms 21612 KB Output is correct
9 Correct 30 ms 21616 KB Output is correct
10 Correct 31 ms 21612 KB Output is correct
11 Correct 31 ms 21616 KB Output is correct
12 Correct 35 ms 21616 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 23168 KB Output is correct
2 Correct 48 ms 23020 KB Output is correct
3 Correct 45 ms 23116 KB Output is correct
4 Correct 51 ms 23020 KB Output is correct
5 Correct 63 ms 22768 KB Output is correct
6 Correct 61 ms 22892 KB Output is correct
7 Correct 49 ms 22892 KB Output is correct
8 Correct 69 ms 22828 KB Output is correct
9 Correct 69 ms 22704 KB Output is correct
10 Correct 61 ms 22892 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 37660 KB Output is correct
2 Correct 232 ms 35568 KB Output is correct
3 Correct 208 ms 36560 KB Output is correct
4 Correct 243 ms 34904 KB Output is correct
5 Correct 495 ms 34724 KB Output is correct
6 Correct 448 ms 34796 KB Output is correct
7 Correct 329 ms 33520 KB Output is correct
8 Correct 589 ms 33880 KB Output is correct
9 Correct 489 ms 34728 KB Output is correct
10 Correct 446 ms 35036 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 635 ms 69948 KB Output is correct
2 Correct 711 ms 61144 KB Output is correct
3 Correct 623 ms 67552 KB Output is correct
4 Correct 729 ms 59644 KB Output is correct
5 Execution timed out 1084 ms 44844 KB Time limit exceeded
6 Halted 0 ms 0 KB -