oj.uz

답안 #162343

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
162343 2019-11-07T15:54:29 Z amoo_safar 회문 (APIO14_palindrome) C++14
39 / 100
 1000 ms 66772 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 f[Maxn], f2[Maxn];

vector<int> V;
stack<int> sta;

ll solve(){
	while(!sta.empty()) sta.pop();
	ll N = V.size();
	//cerr << "N : " << N << '\n';
	sta.push(0);
	for(int i = 1; i < N-1; i++){
		//cerr << i << " " << V[i] << '\n';
		while(V[sta.top()] > V[i]) sta.pop();
		f[i] = sta.top();
		sta.push(i);
	}
	//cerr << "S" << '\n';
	while(!sta.empty()) sta.pop();
	sta.push(N-1);
	for(int i = N-2; i > 0; i--){
		while(V[sta.top()] >= V[i]) sta.pop();
		f2[i] = sta.top();
		sta.push(i);
	}
	ll res = 0;
	
	for(int i = 1; i < N - 1; i++)
		res = max(res, 1LL * (f2[i] - f[i]) * V[i]);
	return res;
}

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;
	//cerr << '\n';
	//for(int i = 0; i < n; i++) cerr << s.substr(idx[i], n) << '\n';
	
	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++) cerr << eq[i] << ' ';
	//cerr << '\n';
	
	
	ll ans = 0;
	
	for(int i = 0; i < n; i++) pal[i] = pal_range(i + 1, i);
	//for(int i = 0; i < n; i++) cerr << pal[i] << ' ';
	//cerr << '\n';
	
	for(int x = 1; x <= n/2; x++){
		ll cnt = (pal[idx[0]] >= x);
		for(int i = 1; i < n; i++){
			if(eq[i - 1] < x) cnt = 0;
			cnt += (pal[idx[i]] >= x);
			ans = max(ans, cnt * (x + x - 1));
		}
	}
	/*
	V.pb(-2);
	for(int i = 0; i < n - 1; i++) V.pb( 2 * min(eq[i], min(pal[idx[i]], pal[idx[i + 1]])) - 1 );
	V.pb(-2);
	//for(auto x : V) cerr << x << ' '; cerr << '\n';
	ans = max(ans, 2LL * (*max_element(pal, pal + n)) - 1);
	
	ans = max(ans, solve());
	*/
	
	for(int i = 0; i < n; i++) pal[i] = pal_range(i, i);
	//for(int i = 0; i < n; i++) cerr << pal[i] << ' ';
	//cerr << '\n';
	/*
	V.clear();
	V.pb(-2);
	for(int i = 0; i < n - 1; i++) V.pb( 2 * min(eq[i], min(pal[idx[i]], pal[idx[i + 1]])) );
	V.pb(-2);
	//for(auto x : V) cerr << x << ' '; cerr << '\n';
	ans = max(ans, 2LL * (*max_element(pal, pal + n)));
	
	ans = max(ans, solve());
	*/
	
	for(int x = 1; x <= n/2; x++){
		ll cnt = (pal[idx[0]] >= x);
		for(int i = 1; i < n; i++){
			if(eq[i - 1] < x) cnt = 0;
			cnt += (pal[idx[i]] >= x);
			ans = max(ans, cnt * (x + x));
		}
	}
	
	cout << ans;
	return 0;
}

/*
abacaba

*/

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 2936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 3192 KB Output is correct
2 Correct 10 ms 3136 KB Output is correct
3 Correct 9 ms 3064 KB Output is correct
4 Correct 10 ms 3064 KB Output is correct
5 Correct 9 ms 3064 KB Output is correct
6 Correct 9 ms 3056 KB Output is correct
7 Correct 11 ms 3064 KB Output is correct
8 Correct 10 ms 3068 KB Output is correct
9 Correct 11 ms 3192 KB Output is correct
10 Correct 12 ms 3064 KB Output is correct
11 Correct 11 ms 3156 KB Output is correct
12 Correct 11 ms 3064 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 223 ms 5092 KB Output is correct
2 Correct 223 ms 5112 KB Output is correct
3 Correct 216 ms 4988 KB Output is correct
4 Correct 505 ms 4984 KB Output is correct
5 Correct 281 ms 5140 KB Output is correct
6 Correct 325 ms 4984 KB Output is correct
7 Correct 223 ms 4984 KB Output is correct
8 Correct 277 ms 5092 KB Output is correct
9 Correct 295 ms 4984 KB Output is correct
10 Correct 293 ms 5112 KB Output is correct

Subtask #4
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1071 ms 24312 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1075 ms 66772 KB Time limit exceeded
2 Halted 0 ms 0 KB -