oj.uz

Submission #388135

# Submission time Handle Problem Language Result Execution time Memory
388135 2021-04-10T08:34:09 Z Keshi Palindromes (APIO14_palindrome) C++17
100 / 100
 390 ms 75964 KB 
//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 < 0) x += mod;
	return x;
}
ll get2(ll l, ll r){
	ll x = hp[r] - hp[l - 1];
	if(x < 0) 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] += j.S;
			if(i >= 2) vec[i - 2][x] = Mp(l, r);
		}
	}
	cout << ans;

    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 33092 KB Output is correct
2 Correct 63 ms 33220 KB Output is correct
3 Correct 63 ms 33068 KB Output is correct
4 Correct 63 ms 33092 KB Output is correct
5 Correct 63 ms 33096 KB Output is correct
6 Correct 64 ms 33168 KB Output is correct
7 Correct 63 ms 33076 KB Output is correct
8 Correct 63 ms 33092 KB Output is correct
9 Correct 63 ms 33224 KB Output is correct
10 Correct 63 ms 33124 KB Output is correct
11 Correct 64 ms 33128 KB Output is correct
12 Correct 65 ms 33092 KB Output is correct
13 Correct 63 ms 33200 KB Output is correct
14 Correct 64 ms 33108 KB Output is correct
15 Correct 63 ms 33136 KB Output is correct
16 Correct 63 ms 33220 KB Output is correct
17 Correct 64 ms 33096 KB Output is correct
18 Correct 65 ms 33128 KB Output is correct
19 Correct 64 ms 33144 KB Output is correct
20 Correct 64 ms 33168 KB Output is correct
21 Correct 63 ms 33176 KB Output is correct
22 Correct 64 ms 33128 KB Output is correct
23 Correct 63 ms 33160 KB Output is correct
24 Correct 63 ms 33092 KB Output is correct
25 Correct 65 ms 33120 KB Output is correct
26 Correct 64 ms 33116 KB Output is correct
27 Correct 63 ms 33236 KB Output is correct
28 Correct 66 ms 33196 KB Output is correct
29 Correct 64 ms 33092 KB Output is correct
30 Correct 64 ms 33224 KB Output is correct
31 Correct 64 ms 33092 KB Output is correct
32 Correct 64 ms 33088 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 33324 KB Output is correct
2 Correct 63 ms 33252 KB Output is correct
3 Correct 64 ms 33224 KB Output is correct
4 Correct 65 ms 33240 KB Output is correct
5 Correct 64 ms 33320 KB Output is correct
6 Correct 64 ms 33232 KB Output is correct
7 Correct 63 ms 33292 KB Output is correct
8 Correct 66 ms 33260 KB Output is correct
9 Correct 65 ms 33292 KB Output is correct
10 Correct 64 ms 33160 KB Output is correct
11 Correct 64 ms 33216 KB Output is correct
12 Correct 64 ms 33188 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 34524 KB Output is correct
2 Correct 70 ms 34548 KB Output is correct
3 Correct 69 ms 34584 KB Output is correct
4 Correct 69 ms 34588 KB Output is correct
5 Correct 73 ms 34496 KB Output is correct
6 Correct 71 ms 34568 KB Output is correct
7 Correct 71 ms 34628 KB Output is correct
8 Correct 69 ms 33400 KB Output is correct
9 Correct 68 ms 33332 KB Output is correct
10 Correct 70 ms 34160 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 47388 KB Output is correct
2 Correct 137 ms 47384 KB Output is correct
3 Correct 123 ms 47348 KB Output is correct
4 Correct 130 ms 47332 KB Output is correct
5 Correct 138 ms 47412 KB Output is correct
6 Correct 134 ms 43988 KB Output is correct
7 Correct 150 ms 45376 KB Output is correct
8 Correct 116 ms 35012 KB Output is correct
9 Correct 120 ms 37796 KB Output is correct
10 Correct 134 ms 45504 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 75752 KB Output is correct
2 Correct 357 ms 75704 KB Output is correct
3 Correct 247 ms 75840 KB Output is correct
4 Correct 358 ms 75704 KB Output is correct
5 Correct 290 ms 75732 KB Output is correct
6 Correct 361 ms 71564 KB Output is correct
7 Correct 390 ms 69476 KB Output is correct
8 Correct 247 ms 38456 KB Output is correct
9 Correct 242 ms 38416 KB Output is correct
10 Correct 284 ms 68900 KB Output is correct
11 Correct 321 ms 75964 KB Output is correct
12 Correct 244 ms 42024 KB Output is correct