oj.uz

답안 #267061

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
267061 2020-08-15T18:43:23 Z amoo_safar 회문 (APIO14_palindrome) C++17
49 / 100
 1000 ms 103652 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 < n; 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
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 35576 KB Output is correct
2 Correct 29 ms 35576 KB Output is correct
3 Correct 30 ms 35576 KB Output is correct
4 Correct 31 ms 35576 KB Output is correct
5 Correct 30 ms 35576 KB Output is correct
6 Correct 31 ms 35568 KB Output is correct
7 Correct 30 ms 35568 KB Output is correct
8 Correct 30 ms 35568 KB Output is correct
9 Correct 30 ms 35572 KB Output is correct
10 Correct 32 ms 35604 KB Output is correct
11 Correct 34 ms 35576 KB Output is correct
12 Correct 32 ms 35568 KB Output is correct
13 Correct 30 ms 35576 KB Output is correct
14 Correct 31 ms 35576 KB Output is correct
15 Correct 30 ms 35576 KB Output is correct
16 Correct 31 ms 35576 KB Output is correct
17 Correct 30 ms 35576 KB Output is correct
18 Correct 30 ms 35568 KB Output is correct
19 Correct 31 ms 35576 KB Output is correct
20 Correct 31 ms 35568 KB Output is correct
21 Correct 35 ms 35568 KB Output is correct
22 Correct 37 ms 35576 KB Output is correct
23 Correct 36 ms 35600 KB Output is correct
24 Correct 35 ms 35576 KB Output is correct
25 Correct 34 ms 35568 KB Output is correct
26 Correct 34 ms 35576 KB Output is correct
27 Correct 34 ms 35576 KB Output is correct
28 Correct 32 ms 35696 KB Output is correct
29 Correct 34 ms 35576 KB Output is correct
30 Correct 30 ms 35568 KB Output is correct
31 Correct 30 ms 35580 KB Output is correct
32 Correct 30 ms 35576 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 35832 KB Output is correct
2 Correct 30 ms 35832 KB Output is correct
3 Correct 31 ms 35824 KB Output is correct
4 Correct 31 ms 35828 KB Output is correct
5 Correct 30 ms 35832 KB Output is correct
6 Correct 31 ms 35828 KB Output is correct
7 Correct 31 ms 35700 KB Output is correct
8 Correct 31 ms 35832 KB Output is correct
9 Correct 31 ms 35820 KB Output is correct
10 Correct 31 ms 35700 KB Output is correct
11 Correct 31 ms 35820 KB Output is correct
12 Correct 31 ms 35820 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 37872 KB Output is correct
2 Correct 47 ms 37740 KB Output is correct
3 Correct 41 ms 37876 KB Output is correct
4 Correct 42 ms 37744 KB Output is correct
5 Correct 41 ms 37492 KB Output is correct
6 Correct 41 ms 37484 KB Output is correct
7 Correct 41 ms 37612 KB Output is correct
8 Correct 51 ms 37680 KB Output is correct
9 Correct 48 ms 37548 KB Output is correct
10 Incorrect 41 ms 37504 KB Output isn't correct

Subtask #4
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 58336 KB Output is correct
2 Correct 166 ms 56300 KB Output is correct
3 Correct 161 ms 57452 KB Output is correct
4 Correct 172 ms 55600 KB Output is correct
5 Correct 177 ms 54708 KB Output is correct
6 Correct 170 ms 55892 KB Output is correct
7 Correct 167 ms 54772 KB Output is correct
8 Correct 469 ms 54668 KB Output is correct
9 Correct 344 ms 55612 KB Output is correct
10 Correct 174 ms 55148 KB Output is correct

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 448 ms 103652 KB Output is correct
2 Correct 465 ms 95160 KB Output is correct
3 Correct 465 ms 101488 KB Output is correct
4 Correct 493 ms 93696 KB Output is correct
5 Correct 508 ms 93200 KB Output is correct
6 Correct 527 ms 93988 KB Output is correct
7 Correct 492 ms 93048 KB Output is correct
8 Execution timed out 1079 ms 69376 KB Time limit exceeded
9 Halted 0 ms 0 KB -