oj.uz

답안 #162356

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
162356 2019-11-07T17:03:57 Z amoo_safar 회문 (APIO14_palindrome) C++14
73 / 100
 1000 ms 69992 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];
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

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 21484 KB Output is correct
2 Correct 28 ms 21608 KB Output is correct
3 Correct 28 ms 21492 KB Output is correct
4 Correct 27 ms 21488 KB Output is correct
5 Correct 27 ms 21484 KB Output is correct
6 Correct 28 ms 21484 KB Output is correct
7 Correct 28 ms 21488 KB Output is correct
8 Correct 28 ms 21484 KB Output is correct
9 Correct 28 ms 21488 KB Output is correct
10 Correct 28 ms 21488 KB Output is correct
11 Correct 28 ms 21488 KB Output is correct
12 Correct 29 ms 21488 KB Output is correct
13 Correct 28 ms 21484 KB Output is correct
14 Correct 28 ms 21484 KB Output is correct
15 Correct 28 ms 21488 KB Output is correct
16 Correct 30 ms 21484 KB Output is correct
17 Correct 31 ms 21484 KB Output is correct
18 Correct 28 ms 21488 KB Output is correct
19 Correct 29 ms 21484 KB Output is correct
20 Correct 30 ms 21488 KB Output is correct
21 Correct 29 ms 21504 KB Output is correct
22 Correct 28 ms 21484 KB Output is correct
23 Correct 29 ms 21544 KB Output is correct
24 Correct 29 ms 21512 KB Output is correct
25 Correct 28 ms 21488 KB Output is correct
26 Correct 28 ms 21452 KB Output is correct
27 Correct 29 ms 21488 KB Output is correct
28 Correct 31 ms 21480 KB Output is correct
29 Correct 29 ms 21472 KB Output is correct
30 Correct 29 ms 21492 KB Output is correct
31 Correct 28 ms 21488 KB Output is correct
32 Correct 28 ms 21484 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 21608 KB Output is correct
2 Correct 42 ms 21612 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 21612 KB Output is correct
6 Correct 31 ms 21608 KB Output is correct
7 Correct 30 ms 21612 KB Output is correct
8 Correct 29 ms 21612 KB Output is correct
9 Correct 31 ms 21592 KB Output is correct
10 Correct 31 ms 21616 KB Output is correct
11 Correct 30 ms 21660 KB Output is correct
12 Correct 31 ms 21616 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 23148 KB Output is correct
2 Correct 49 ms 22936 KB Output is correct
3 Correct 47 ms 23044 KB Output is correct
4 Correct 50 ms 23020 KB Output is correct
5 Correct 63 ms 22892 KB Output is correct
6 Correct 62 ms 22804 KB Output is correct
7 Correct 49 ms 22896 KB Output is correct
8 Correct 72 ms 22816 KB Output is correct
9 Correct 67 ms 22832 KB Output is correct
10 Correct 61 ms 22764 KB Output is correct

Subtask #4
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 218 ms 37608 KB Output is correct
2 Correct 229 ms 35568 KB Output is correct
3 Correct 208 ms 36592 KB Output is correct
4 Correct 242 ms 34856 KB Output is correct
5 Correct 484 ms 34672 KB Output is correct
6 Correct 431 ms 34668 KB Output is correct
7 Correct 338 ms 33520 KB Output is correct
8 Correct 586 ms 33884 KB Output is correct
9 Correct 507 ms 34692 KB Output is correct
10 Correct 442 ms 35056 KB Output is correct

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 653 ms 69992 KB Output is correct
2 Correct 713 ms 61172 KB Output is correct
3 Correct 607 ms 67612 KB Output is correct
4 Correct 702 ms 59780 KB Output is correct
5 Execution timed out 1079 ms 44716 KB Time limit exceeded
6 Halted 0 ms 0 KB -