oj.uz

Submission #162355

# Submission time Handle Problem Language Result Execution time Memory
162355 2019-11-07T17:02:06 Z amoo_safar Palindromes (APIO14_palindrome) C++14
23 / 100
 1000 ms 70076 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 = (1 << 30) - 1;
const int Maxn = 3e5 + 10;
const int Maxk = 60;
const ll Inf = 2242545357980376863LL;
const ll Log = 20;
const ll Base = 101;

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;
}
ll get_rev(int l, int r){
	return (phr[l] - (phr[r]*pw[r - l] )) & 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 27 ms 21616 KB Output is correct
2 Correct 28 ms 21488 KB Output is correct
3 Correct 26 ms 21484 KB Output is correct
4 Correct 26 ms 21488 KB Output is correct
5 Correct 27 ms 21488 KB Output is correct
6 Correct 30 ms 21484 KB Output is correct
7 Correct 27 ms 21488 KB Output is correct
8 Correct 46 ms 21516 KB Output is correct
9 Correct 29 ms 21656 KB Output is correct
10 Correct 29 ms 21484 KB Output is correct
11 Correct 27 ms 21488 KB Output is correct
12 Correct 27 ms 21488 KB Output is correct
13 Correct 26 ms 21488 KB Output is correct
14 Correct 28 ms 21488 KB Output is correct
15 Correct 26 ms 21484 KB Output is correct
16 Correct 29 ms 21492 KB Output is correct
17 Correct 29 ms 21484 KB Output is correct
18 Correct 28 ms 21488 KB Output is correct
19 Correct 28 ms 21488 KB Output is correct
20 Correct 36 ms 21488 KB Output is correct
21 Correct 28 ms 21488 KB Output is correct
22 Correct 27 ms 21628 KB Output is correct
23 Correct 29 ms 21484 KB Output is correct
24 Correct 29 ms 21484 KB Output is correct
25 Correct 29 ms 21488 KB Output is correct
26 Correct 28 ms 21480 KB Output is correct
27 Correct 26 ms 21488 KB Output is correct
28 Correct 27 ms 21520 KB Output is correct
29 Correct 27 ms 21480 KB Output is correct
30 Correct 26 ms 21492 KB Output is correct
31 Correct 29 ms 21488 KB Output is correct
32 Correct 26 ms 21488 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 21608 KB Output is correct
2 Correct 29 ms 21640 KB Output is correct
3 Correct 28 ms 21612 KB Output is correct
4 Correct 29 ms 21612 KB Output is correct
5 Correct 30 ms 21600 KB Output is correct
6 Correct 30 ms 21608 KB Output is correct
7 Correct 31 ms 21616 KB Output is correct
8 Correct 29 ms 21612 KB Output is correct
9 Correct 29 ms 21620 KB Output is correct
10 Correct 31 ms 21616 KB Output is correct
11 Correct 30 ms 21612 KB Output is correct
12 Correct 31 ms 21616 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 23120 KB Output is correct
2 Correct 43 ms 23020 KB Output is correct
3 Correct 40 ms 23080 KB Output is correct
4 Correct 48 ms 23024 KB Output is correct
5 Correct 58 ms 22864 KB Output is correct
6 Correct 55 ms 22760 KB Output is correct
7 Correct 44 ms 22764 KB Output is correct
8 Correct 65 ms 22704 KB Output is correct
9 Correct 68 ms 22700 KB Output is correct
10 Incorrect 56 ms 22764 KB Output isn't correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 37656 KB Output is correct
2 Correct 199 ms 35748 KB Output is correct
3 Correct 180 ms 36620 KB Output is correct
4 Correct 212 ms 34800 KB Output is correct
5 Correct 487 ms 34660 KB Output is correct
6 Correct 406 ms 34796 KB Output is correct
7 Correct 307 ms 33548 KB Output is correct
8 Correct 550 ms 33816 KB Output is correct
9 Correct 459 ms 34732 KB Output is correct
10 Incorrect 401 ms 34792 KB Output isn't correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 70076 KB Output is correct
2 Correct 591 ms 61096 KB Output is correct
3 Correct 493 ms 67584 KB Output is correct
4 Correct 591 ms 59804 KB Output is correct
5 Execution timed out 1080 ms 44748 KB Time limit exceeded
6 Halted 0 ms 0 KB -