oj.uz

답안 #162345

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
162345 2019-11-07T15:57:04 Z amoo_safar 회문 (APIO14_palindrome) C++14
39 / 100
 1000 ms 66532 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; 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; 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 Correct 6 ms 2936 KB Output is correct
2 Correct 18 ms 2936 KB Output is correct
3 Correct 6 ms 2908 KB Output is correct
4 Incorrect 6 ms 2808 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 526 ms 5132 KB Output is correct
2 Correct 418 ms 5080 KB Output is correct
3 Correct 418 ms 4984 KB Output is correct
4 Correct 428 ms 5080 KB Output is correct
5 Correct 530 ms 4984 KB Output is correct
6 Correct 500 ms 4984 KB Output is correct
7 Correct 442 ms 4984 KB Output is correct
8 Correct 514 ms 5112 KB Output is correct
9 Correct 511 ms 4984 KB Output is correct
10 Correct 528 ms 5112 KB Output is correct

Subtask #4
0 / 26.0

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

Subtask #5
0 / 27.0

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