oj.uz

답안 #162350

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
162350 2019-11-07T16:19:24 Z amoo_safar 회문 (APIO14_palindrome) C++14
73 / 100
 1000 ms 103796 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'
#define int ll

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

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 25960 KB Output is correct
2 Correct 34 ms 25960 KB Output is correct
3 Correct 34 ms 25960 KB Output is correct
4 Correct 33 ms 25960 KB Output is correct
5 Correct 33 ms 25960 KB Output is correct
6 Correct 34 ms 25964 KB Output is correct
7 Correct 34 ms 26088 KB Output is correct
8 Correct 76 ms 25888 KB Output is correct
9 Correct 34 ms 25960 KB Output is correct
10 Correct 35 ms 25964 KB Output is correct
11 Correct 34 ms 25972 KB Output is correct
12 Correct 59 ms 25948 KB Output is correct
13 Correct 34 ms 25960 KB Output is correct
14 Correct 34 ms 25960 KB Output is correct
15 Correct 38 ms 25960 KB Output is correct
16 Correct 34 ms 25960 KB Output is correct
17 Correct 35 ms 25960 KB Output is correct
18 Correct 34 ms 25960 KB Output is correct
19 Correct 37 ms 25960 KB Output is correct
20 Correct 90 ms 25964 KB Output is correct
21 Correct 34 ms 25960 KB Output is correct
22 Correct 34 ms 25960 KB Output is correct
23 Correct 34 ms 25924 KB Output is correct
24 Correct 34 ms 25960 KB Output is correct
25 Correct 34 ms 25960 KB Output is correct
26 Correct 34 ms 25960 KB Output is correct
27 Correct 34 ms 25964 KB Output is correct
28 Correct 34 ms 26088 KB Output is correct
29 Correct 36 ms 25960 KB Output is correct
30 Correct 38 ms 25932 KB Output is correct
31 Correct 35 ms 25960 KB Output is correct
32 Correct 34 ms 25960 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 26212 KB Output is correct
2 Correct 37 ms 26092 KB Output is correct
3 Correct 35 ms 26164 KB Output is correct
4 Correct 36 ms 26212 KB Output is correct
5 Correct 36 ms 26212 KB Output is correct
6 Correct 35 ms 26212 KB Output is correct
7 Correct 37 ms 26088 KB Output is correct
8 Correct 38 ms 26212 KB Output is correct
9 Correct 37 ms 26216 KB Output is correct
10 Correct 38 ms 26092 KB Output is correct
11 Correct 38 ms 26220 KB Output is correct
12 Correct 39 ms 26212 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 28552 KB Output is correct
2 Correct 55 ms 28408 KB Output is correct
3 Correct 51 ms 28488 KB Output is correct
4 Correct 59 ms 28392 KB Output is correct
5 Correct 72 ms 28424 KB Output is correct
6 Correct 67 ms 28376 KB Output is correct
7 Correct 56 ms 28388 KB Output is correct
8 Correct 79 ms 28392 KB Output is correct
9 Correct 77 ms 28264 KB Output is correct
10 Correct 69 ms 28388 KB Output is correct

Subtask #4
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 239 ms 51876 KB Output is correct
2 Correct 255 ms 50324 KB Output is correct
3 Correct 229 ms 50060 KB Output is correct
4 Correct 269 ms 48492 KB Output is correct
5 Correct 564 ms 49828 KB Output is correct
6 Correct 485 ms 50284 KB Output is correct
7 Correct 372 ms 47980 KB Output is correct
8 Correct 654 ms 49832 KB Output is correct
9 Correct 548 ms 49552 KB Output is correct
10 Correct 492 ms 51024 KB Output is correct

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 703 ms 103796 KB Output is correct
2 Correct 803 ms 97908 KB Output is correct
3 Correct 705 ms 99692 KB Output is correct
4 Correct 820 ms 94336 KB Output is correct
5 Execution timed out 1071 ms 59856 KB Time limit exceeded
6 Halted 0 ms 0 KB -