Submission #388132

#	Time	Username	Problem	Language	Result	Execution time	Memory
388132		Keshi	Palindromes (APIO14_palindrome)	C++17	0 / 100	920 ms	131076 KiB

palindrome

//In the name of God
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll maxn = 3e5 + 100;
const ll mod = 1e9 + 7;
const ll base = 31;
const ll inf = 1e18;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
#define lc (id << 1)
#define rc (lc | 1)

ll pw(ll a, ll b){
	ll c = 1;
	while(b){
		if(b & 1) c = c * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return c;
}

ll n, h[maxn], hp[maxn], p[maxn], pp[maxn];
string s;
map<ll, ll> cnt[maxn];
map<ll, pll> vec[maxn];

ll get1(ll l, ll r){
	ll x = (h[r] - h[l - 1] * p[r - l + 1]) % mod;
	if(x >= mod) x -= mod;
	return x;
}
ll get2(ll l, ll r){
	ll x = hp[r] - hp[l - 1];
	if(x >= mod) x -= mod;
	return x * pp[l] % mod;
}
bool ok(ll l, ll r){
	if(l < 1 || r > n) return 0;
	return (get1(l, r) == get2(l, r));
}

int main(){
	p[0] = pp[0] = 1;
	for(ll i = 1; i < maxn; i++){
		p[i] = p[i - 1] * base % mod;
		pp[i] = pw(p[i], mod - 2);
	}
	cin >> s;
	n = Sz(s);
	s = ' ' + s;
	for(ll i = 1; i <= n; i++){
		h[i] = (h[i - 1] * base + ll(s[i] - 'a')) % mod;
		hp[i] = (hp[i - 1] + p[i] * ll(s[i] - 'a')) % mod;
	}
	for(ll i = 1; i <= n; i++){
		ll l = 0, r = n;
		while(r - l > 1){
			ll mid = (l + r) >> 1;
			if(ok(i - mid, i + mid)) l = mid;
			else r = mid;
		}
		ll x = get1(i - l, i + l);
		cnt[l * 2 + 1][x]++;
		vec[l * 2 + 1][x] = Mp(i - l, i + l);
	}
	for(ll i = 1; i <= n; i++){
		ll l = 0, r = n;
		while(r - l > 1){
			ll mid = (l + r) >> 1;
			if(ok(i - mid + 1, i + mid)) l = mid;
			else r = mid;
		}
		if(l == 0) continue;
		ll x = get1(i - l + 1, i + l);
		cnt[l * 2][x]++;
		vec[l * 2][x] = Mp(i - l + 1, i + l);
	}
	ll ans = 0;
	for(ll i = n; i > 0; i--){
		for(pll j : cnt[i]){
			ans = max(ans, i * j.S);
			ll l = vec[i][j.F].F + 1;
			ll r = vec[i][j.F].S - 1;
			ll x = get1(l, r);
			if(i >= 2) cnt[i - 2][x] += cnt[i][x];
			if(i >= 2) vec[i - 2][x] = Mp(l, r);
		}
	}
	cout << ans;

    return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27